oj.uz

답안 #2684

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

#define BUCKET_SIZE 351

int s[123456];
int e[123456];

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%BUCKET_SIZE==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%BUCKET_SIZE))
{
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<j*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 2200 KB Output is correct
2 Correct 0 ms 2200 KB Output is correct
3 Correct 0 ms 2200 KB Output is correct
4 Correct 0 ms 2200 KB Output is correct
5 Correct 0 ms 2200 KB Output is correct
6 Correct 0 ms 2200 KB Output is correct
7 Correct 0 ms 2200 KB Output is correct
8 Correct 0 ms 2200 KB Output is correct
9 Correct 0 ms 2200 KB Output is correct
10 Correct 0 ms 2200 KB Output is correct
11 Correct 0 ms 2200 KB Output is correct
12 Correct 0 ms 2200 KB Output is correct
13 Correct 0 ms 2200 KB Output is correct
14 Correct 0 ms 2200 KB Output is correct
15 Correct 0 ms 2200 KB Output is correct
16 Correct 0 ms 2200 KB Output is correct
17 Correct 0 ms 2200 KB Output is correct
18 Correct 0 ms 2200 KB Output is correct
19 Correct 0 ms 2200 KB Output is correct
20 Correct 0 ms 2200 KB Output is correct
21 Correct 0 ms 2200 KB Output is correct
22 Correct 0 ms 2200 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 2464 KB Output is correct
2 Correct 48 ms 2464 KB Output is correct
3 Correct 48 ms 2464 KB Output is correct
4 Correct 60 ms 3256 KB Output is correct
5 Correct 52 ms 3256 KB Output is correct
6 Correct 444 ms 3256 KB Output is correct
7 Correct 420 ms 3256 KB Output is correct
8 Correct 432 ms 3124 KB Output is correct
9 Correct 56 ms 2200 KB Output is correct
10 Correct 60 ms 2200 KB Output is correct
11 Correct 56 ms 2200 KB Output is correct
12 Correct 56 ms 3256 KB Output is correct
13 Correct 56 ms 3256 KB Output is correct
14 Correct 56 ms 3256 KB Output is correct
15 Correct 36 ms 2200 KB Output is correct
16 Correct 48 ms 2200 KB Output is correct
17 Correct 12 ms 2200 KB Output is correct
18 Correct 8 ms 2200 KB Output is correct
19 Correct 8 ms 2200 KB Output is correct
20 Correct 4 ms 2200 KB Output is correct
21 Correct 4 ms 2200 KB Output is correct
22 Correct 4 ms 2200 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1408 ms 4508 KB Output is correct
2 Correct 1400 ms 4372 KB Output is correct
3 Correct 1388 ms 7756 KB Output is correct
4 Correct 1448 ms 4508 KB Output is correct
5 Correct 1608 ms 3552 KB Output is correct
6 Correct 1388 ms 7756 KB Output is correct
7 Correct 1496 ms 3416 KB Output is correct
8 Correct 1596 ms 3552 KB Output is correct
9 Correct 2108 ms 2332 KB Output is correct
10 Correct 2112 ms 2332 KB Output is correct
11 Correct 1516 ms 3412 KB Output is correct
12 Correct 1328 ms 7756 KB Output is correct
13 Correct 1388 ms 5316 KB Output is correct
14 Correct 1380 ms 5320 KB Output is correct
15 Correct 1716 ms 2200 KB Output is correct
16 Correct 1496 ms 2200 KB Output is correct
17 Correct 528 ms 2200 KB Output is correct
18 Correct 504 ms 2200 KB Output is correct
19 Correct 176 ms 2200 KB Output is correct
20 Correct 176 ms 2200 KB Output is correct
21 Correct 120 ms 2200 KB Output is correct
22 Correct 120 ms 2200 KB Output is correct