oj.uz

답안 #2683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2683 2013-07-30T15:04:22 Z gs13068 간선 파괴 (GA5_destroy) C++
100 / 100
 2172 ms 6592 KB 
#include<cstdio>
#include<vector>

#define BUCKET_SIZE 9

int s[200000];
int e[200000];

struct edge
{
int s;
int e;
} temp;

std::vector<edge> pre[400];
std::vector<edge> suf[400];
int parent[1000];
int height[1000];

inline int root(int x)
{
return parent[x]==x?x:parent[x]=root(parent[x]);
}

inline void combine(int a,int b)
{
a=root(a);
b=root(b);
if(a==b)return;
if(height[a]<height[b])parent[a]=b;
else parent[b]=a;
if(height[a]==height[b])height[b]++;
}

int main()
{
int i,j,k,n,m,l,r,q;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d",&s[i],&e[i]);
s[i]--;e[i]--;
}
for(i=0;i<n;i++)
{
parent[i]=i;
height[i]=0;
}
for(i=0;i<m;i++)
{
combine(s[i],e[i]);
if((i&((1<<BUCKET_SIZE)-1))==(1<<BUCKET_SIZE)-1)
{
for(j=0;j<n;j++)if(parent[j]!=j)
{
temp.s=j;
temp.e=parent[j];
pre[i>>BUCKET_SIZE].push_back(temp);
}
}
}
for(i=0;i<n;i++)
{
parent[i]=i;
height[i]=0;
}
for(i=m-1;i>=0;i--)
{
combine(s[i],e[i]);
if(!(i&((1<<BUCKET_SIZE)-1)))
{
for(j=0;j<n;j++)if(parent[j]!=j)
{
temp.s=j;
temp.e=parent[j];
suf[i>>BUCKET_SIZE].push_back(temp);
}
}
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&l,&r);
l--;r--;
for(j=0;j<n;j++)
{
parent[j]=j;
height[j]=0;
}
j=(l>>BUCKET_SIZE)-1;
if(j>=0)for(k=0;k<pre[j].size();k++)combine(pre[j][k].s,pre[j][k].e);
for(k=(l>>BUCKET_SIZE)<<BUCKET_SIZE;k<l;k++)combine(s[k],e[k]);
j=(r>>BUCKET_SIZE)+1;
for(k=0;k<suf[j].size();k++)combine(suf[j][k].s,suf[j][k].e);
for(k=r+1;k<((r>>BUCKET_SIZE)+1)<<BUCKET_SIZE;k++)combine(s[k],e[k]);
k=0;
for(j=0;j<n;j++)if(parent[j]==j)k++;
printf("%d\n",k);
}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2800 KB Output is correct
2 Correct 0 ms 2800 KB Output is correct
3 Correct 0 ms 2800 KB Output is correct
4 Correct 0 ms 2800 KB Output is correct
5 Correct 0 ms 2800 KB Output is correct
6 Correct 0 ms 2800 KB Output is correct
7 Correct 0 ms 2800 KB Output is correct
8 Correct 0 ms 2800 KB Output is correct
9 Correct 0 ms 2800 KB Output is correct
10 Correct 0 ms 2800 KB Output is correct
11 Correct 0 ms 2800 KB Output is correct
12 Correct 0 ms 2800 KB Output is correct
13 Correct 0 ms 2800 KB Output is correct
14 Correct 0 ms 2800 KB Output is correct
15 Correct 0 ms 2800 KB Output is correct
16 Correct 0 ms 2800 KB Output is correct
17 Correct 0 ms 2800 KB Output is correct
18 Correct 0 ms 2800 KB Output is correct
19 Correct 0 ms 2800 KB Output is correct
20 Correct 0 ms 2800 KB Output is correct
21 Correct 0 ms 2800 KB Output is correct
22 Correct 0 ms 2800 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 2932 KB Output is correct
2 Correct 52 ms 2932 KB Output is correct
3 Correct 48 ms 2932 KB Output is correct
4 Correct 52 ms 3460 KB Output is correct
5 Correct 52 ms 3460 KB Output is correct
6 Correct 472 ms 3460 KB Output is correct
7 Correct 452 ms 3460 KB Output is correct
8 Correct 448 ms 3460 KB Output is correct
9 Correct 56 ms 2800 KB Output is correct
10 Correct 56 ms 2800 KB Output is correct
11 Correct 56 ms 2800 KB Output is correct
12 Correct 52 ms 3460 KB Output is correct
13 Correct 52 ms 3460 KB Output is correct
14 Correct 52 ms 3460 KB Output is correct
15 Correct 36 ms 2800 KB Output is correct
16 Correct 48 ms 2800 KB Output is correct
17 Correct 12 ms 2800 KB Output is correct
18 Correct 12 ms 2800 KB Output is correct
19 Correct 8 ms 2800 KB Output is correct
20 Correct 4 ms 2800 KB Output is correct
21 Correct 4 ms 2800 KB Output is correct
22 Correct 4 ms 2800 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1464 ms 4420 KB Output is correct
2 Correct 1456 ms 4284 KB Output is correct
3 Correct 1408 ms 6592 KB Output is correct
4 Correct 1516 ms 4284 KB Output is correct
5 Correct 1644 ms 3608 KB Output is correct
6 Correct 1404 ms 6592 KB Output is correct
7 Correct 1552 ms 3608 KB Output is correct
8 Correct 1624 ms 3608 KB Output is correct
9 Correct 2160 ms 2800 KB Output is correct
10 Correct 2172 ms 2800 KB Output is correct
11 Correct 1564 ms 3608 KB Output is correct
12 Correct 1436 ms 6592 KB Output is correct
13 Correct 1460 ms 4972 KB Output is correct
14 Correct 1416 ms 4972 KB Output is correct
15 Correct 1700 ms 2800 KB Output is correct
16 Correct 1472 ms 2800 KB Output is correct
17 Correct 504 ms 2800 KB Output is correct
18 Correct 444 ms 2800 KB Output is correct
19 Correct 248 ms 2800 KB Output is correct
20 Correct 188 ms 2800 KB Output is correct
21 Correct 140 ms 2800 KB Output is correct
22 Correct 140 ms 2800 KB Output is correct