oj.uz

답안 #2671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2671 2013-07-30T13:59:25 Z gs13068 간선 파괴 (GA5_destroy) C++
100 / 100
 1612 ms 7380 KB 
#include<cstdio>
#include<vector>

#define BUCKET_SIZE 9

int s[300000];
int e[300000];

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

std::vector<edge> pre[600];
std::vector<edge> suf[600];
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(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 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Correct 0 ms 3588 KB Output is correct
5 Correct 0 ms 3588 KB Output is correct
6 Correct 0 ms 3588 KB Output is correct
7 Correct 0 ms 3588 KB Output is correct
8 Correct 0 ms 3588 KB Output is correct
9 Correct 0 ms 3588 KB Output is correct
10 Correct 0 ms 3588 KB Output is correct
11 Correct 0 ms 3588 KB Output is correct
12 Correct 0 ms 3588 KB Output is correct
13 Correct 0 ms 3588 KB Output is correct
14 Correct 0 ms 3588 KB Output is correct
15 Correct 0 ms 3588 KB Output is correct
16 Correct 0 ms 3588 KB Output is correct
17 Correct 0 ms 3588 KB Output is correct
18 Correct 0 ms 3588 KB Output is correct
19 Correct 0 ms 3588 KB Output is correct
20 Correct 0 ms 3588 KB Output is correct
21 Correct 0 ms 3588 KB Output is correct
22 Correct 0 ms 3588 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 3720 KB Output is correct
2 Correct 44 ms 3720 KB Output is correct
3 Correct 48 ms 3720 KB Output is correct
4 Correct 60 ms 4248 KB Output is correct
5 Correct 56 ms 4248 KB Output is correct
6 Correct 480 ms 4248 KB Output is correct
7 Correct 456 ms 4248 KB Output is correct
8 Correct 464 ms 4248 KB Output is correct
9 Correct 40 ms 3588 KB Output is correct
10 Correct 40 ms 3588 KB Output is correct
11 Correct 36 ms 3588 KB Output is correct
12 Correct 60 ms 4248 KB Output is correct
13 Correct 56 ms 4248 KB Output is correct
14 Correct 48 ms 4248 KB Output is correct
15 Correct 28 ms 3588 KB Output is correct
16 Correct 32 ms 3588 KB Output is correct
17 Correct 12 ms 3588 KB Output is correct
18 Correct 12 ms 3588 KB Output is correct
19 Correct 8 ms 3588 KB Output is correct
20 Correct 4 ms 3588 KB Output is correct
21 Correct 4 ms 3588 KB Output is correct
22 Correct 4 ms 3588 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1612 ms 5208 KB Output is correct
2 Correct 1476 ms 5072 KB Output is correct
3 Correct 1508 ms 7380 KB Output is correct
4 Correct 1456 ms 5072 KB Output is correct
5 Correct 1476 ms 4396 KB Output is correct
6 Correct 1484 ms 7380 KB Output is correct
7 Correct 1460 ms 4396 KB Output is correct
8 Correct 1536 ms 4396 KB Output is correct
9 Correct 1408 ms 3588 KB Output is correct
10 Correct 1496 ms 3588 KB Output is correct
11 Correct 1460 ms 4396 KB Output is correct
12 Correct 1500 ms 7380 KB Output is correct
13 Correct 1468 ms 5760 KB Output is correct
14 Correct 1504 ms 5760 KB Output is correct
15 Correct 1204 ms 3588 KB Output is correct
16 Correct 1076 ms 3588 KB Output is correct
17 Correct 512 ms 3588 KB Output is correct
18 Correct 432 ms 3588 KB Output is correct
19 Correct 264 ms 3588 KB Output is correct
20 Correct 208 ms 3588 KB Output is correct
21 Correct 172 ms 3588 KB Output is correct
22 Correct 176 ms 3588 KB Output is correct