SIO 2017 OS resenja

Pitanja i problemi
1

Moze li neko postaviti resenja SIO 2017 za OS (zanimaju me posebno prvi i treci zadatak jer sam drugi vec sam uradio na takmicenju)?

3

Evo mog resenja prvog zad:
#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000000

map <int,int> hsh;
int he=1;
int n,m,N;
vector g[MAXN];
bool bio[MAXN];
bool oduzet[MAXN];
int x1,x2;

void dfs(int index)
{
if(bio[index])return ;
bio[index]=1;
for(int i = 0; i < g[index].size();i++)dfs(g[index][i]);
}

int main()
{
scanf("%d%d",&n,&m);
N = n;
for(int i = 0; i < m; i++)
{
scanf("%d%d",&x1,&x2);
if(!hsh[x1])hsh[x1]=he,he++;
if(!hsh[x2])hsh[x2]=he,he++;
g[hsh[x1]].push_back(hsh[x2]);
g[hsh[x2]].push_back(hsh[x1]);
if(!oduzet[hsh[x1]])N–;
if(!oduzet[hsh[x2]])N–;
oduzet[hsh[x1]]=1;
oduzet[hsh[x2]]=1;
}
for(int i = 1; i < he; i++)
{
if(!bio[i])dfs(i),N++;
}
printf("%d",N);
return 0;
}

4

Hvala! Da li mozda znas i resenje treceg zad?

5

Mozes li postaviti tekst/link 3. zadatka?

6

http://petlja.org/competitions/competition/33
Ovaj zadatak podcifra

7

Evo treceg zad:

#include <bits/stdc++.h>
using namespace std;

struct qu
{
int k;
int c;
int id;
};
struct cmp
{
bool operator()(qu a,qu b)
{
return a.k<b.k;
}
};
priority_queue <qu,vector,cmp> pq;

int n,m;
char broj[100005];
char out[100005];
int a[100005];
int b[100005];
int x1,x2;
qu qq;

int main() {
// your code goes here
scanf("%s",&broj);
n=strlen(broj);
for(int i = 0; i < n; i++)a[i]=broj[i]-‘0’;
scanf("%d",&m);
for(int i = 0; i < m; i++)
{
scanf("%d%d",&x1,&x2);
qq.k=x1;
qq.c=x2-1;
qq.id=i;
pq.push(qq);
}
int pos=0,pom=0;
for(int k = n; k > 0; k–)
{
while(!pq.empty() && pq.top().k==k)
{
qq=pq.top();
pq.pop();
if(qq.c<pom)out[qq.id]=b[qq.c]+‘0’;
else out[qq.id]=a[pos+qq.c-pom]+‘0’;
}
while( pos<n && ( pom==0 || b[pom-1] >= a[pos] ) )b[pom++]=a[pos++]; //pos < n i (pom je nula ili b[pom-1] >= a[pos]
pom–;
}
printf("%s",out);
return 0;
}

8

Kako u glasili zadaci, jel se secate?

1 Like