oj.uz

답안 #2681

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

#define BUCKET_SIZE 400

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

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

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 3068 KB Output is correct
2 Correct 52 ms 3068 KB Output is correct
3 Correct 52 ms 3068 KB Output is correct
4 Correct 56 ms 3728 KB Output is correct
5 Correct 56 ms 3728 KB Output is correct
6 Correct 444 ms 3728 KB Output is correct
7 Correct 420 ms 3728 KB Output is correct
8 Correct 428 ms 3596 KB Output is correct
9 Correct 56 ms 2804 KB Output is correct
10 Correct 56 ms 2804 KB Output is correct
11 Correct 56 ms 2804 KB Output is correct
12 Correct 56 ms 3728 KB Output is correct
13 Correct 52 ms 3728 KB Output is correct
14 Correct 56 ms 3728 KB Output is correct
15 Correct 40 ms 2804 KB Output is correct
16 Correct 52 ms 2804 KB Output is correct
17 Correct 12 ms 2804 KB Output is correct
18 Correct 8 ms 2804 KB Output is correct
19 Correct 8 ms 2804 KB Output is correct
20 Correct 4 ms 2804 KB Output is correct
21 Correct 4 ms 2804 KB Output is correct
22 Correct 4 ms 2804 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1432 ms 4832 KB Output is correct
2 Correct 1448 ms 4696 KB Output is correct
3 Correct 1400 ms 7684 KB Output is correct
4 Correct 1520 ms 4832 KB Output is correct
5 Correct 1648 ms 3888 KB Output is correct
6 Correct 1424 ms 7684 KB Output is correct
7 Correct 1520 ms 3884 KB Output is correct
8 Correct 1608 ms 3884 KB Output is correct
9 Correct 2164 ms 2936 KB Output is correct
10 Correct 2128 ms 2936 KB Output is correct
11 Correct 1492 ms 3884 KB Output is correct
12 Correct 1400 ms 7684 KB Output is correct
13 Correct 1360 ms 5516 KB Output is correct
14 Correct 1408 ms 5648 KB Output is correct
15 Correct 1724 ms 2804 KB Output is correct
16 Correct 1480 ms 2804 KB Output is correct
17 Correct 520 ms 2804 KB Output is correct
18 Correct 504 ms 2804 KB Output is correct
19 Correct 192 ms 2804 KB Output is correct
20 Correct 180 ms 2804 KB Output is correct
21 Correct 116 ms 2804 KB Output is correct
22 Correct 124 ms 2804 KB Output is correct