oj.uz

답안 #2673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2673 2013-07-30T14:44:06 Z gs13068 간선 파괴 (GA5_destroy) C++
100 / 100
 1504 ms 11192 KB 
#include<cstdio>
#include<vector>

#define BUCKET_SIZE 8

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 44 ms 3984 KB Output is correct
2 Correct 40 ms 3984 KB Output is correct
3 Correct 44 ms 3984 KB Output is correct
4 Correct 44 ms 5040 KB Output is correct
5 Correct 56 ms 5040 KB Output is correct
6 Correct 444 ms 5040 KB Output is correct
7 Correct 408 ms 4908 KB Output is correct
8 Correct 420 ms 4908 KB Output is correct
9 Correct 32 ms 3588 KB Output is correct
10 Correct 36 ms 3588 KB Output is correct
11 Correct 40 ms 3588 KB Output is correct
12 Correct 52 ms 5040 KB Output is correct
13 Correct 52 ms 5040 KB Output is correct
14 Correct 52 ms 5040 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 8 ms 3588 KB Output is correct
19 Correct 4 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 1504 ms 6712 KB Output is correct
2 Correct 1336 ms 6576 KB Output is correct
3 Correct 1396 ms 11192 KB Output is correct
4 Correct 1356 ms 6712 KB Output is correct
5 Correct 1388 ms 5356 KB Output is correct
6 Correct 1416 ms 11192 KB Output is correct
7 Correct 1332 ms 5220 KB Output is correct
8 Correct 1396 ms 5356 KB Output is correct
9 Correct 1296 ms 3724 KB Output is correct
10 Correct 1424 ms 3724 KB Output is correct
11 Correct 1304 ms 5220 KB Output is correct
12 Correct 1396 ms 11192 KB Output is correct
13 Correct 1316 ms 7932 KB Output is correct
14 Correct 1344 ms 7932 KB Output is correct
15 Correct 1192 ms 3588 KB Output is correct
16 Correct 1068 ms 3588 KB Output is correct
17 Correct 508 ms 3588 KB Output is correct
18 Correct 460 ms 3588 KB Output is correct
19 Correct 144 ms 3588 KB Output is correct
20 Correct 180 ms 3588 KB Output is correct
21 Correct 132 ms 3588 KB Output is correct
22 Correct 124 ms 3588 KB Output is correct