| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 3004 |
2013-08-22T10:05:29 Z |
cki86201 |
간선 파괴 (GA5_destroy) |
C++ |
|
84 ms |
6972 KB |
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<functional>
using namespace std;
// O(Q+V^2) method;
const int ME = 250000;
const int MV = 710;
const int INF = 0x7fffffff;
int A[ME],B[ME];
int p[MV],Rank[MV];
int E,V;
int D[MV][MV];
int tox[MV],toy[MV],lx,ly;
int ix[ME],iy[ME];
void init(){for(int i=1;i<=V;i++)p[i]=i,Rank[i]=1;}
int Find(int x)
{
int a=x;
while(p[x]!=x)x=p[x];
while(a!=x){a=p[a];p[a]=x;}
return x;
}
bool Union(int x,int y)
{
x=Find(x), y=Find(y);
if(Rank[x]>Rank[y])p[y]=p[x],Rank[x]+=Rank[y],Rank[y]=0;
else p[x]=p[y],Rank[y]+=Rank[x],Rank[x]=0;
return x==y;
}
int main()
{
scanf("%d%d",&V,&E);
int i,j;
for(i=1;i<=E;i++)scanf("%d%d",A+i,B+i);
init();
for(i=1;i<=E;i++){
if(!Union(A[i],B[i]))tox[++lx]=i;
}
init();
for(i=E;i;i--){
if(!Union(A[i],B[i]))toy[++ly]=i;
}
for(i=1;i<=lx+1;i++){
int cnt=V;
init();
for(j=1;j<i;j++)if(!Union(A[tox[j]],B[tox[j]]))--cnt;
for(j=1;j<=ly;j++){
D[i][j]=cnt;
if(!Union(A[toy[j]],B[toy[j]]))--cnt;
}
D[i][ly+1]=cnt;
}
for(i=1,j=1;i<=E;i++){
ix[i]=j;
if(tox[j]==i)j++;
}
for(i=E,j=1;i;i--){
iy[i]=j;
if(toy[j]==i)j++;
}
int q;scanf("%d",&q);
while(q--){
int x,y;scanf("%d%d",&x,&y);
x=ix[x],y=iy[y];
printf("%d\n",D[x][y]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 8 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 9 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 10 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 11 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 12 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 13 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 14 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 15 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 16 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 17 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 18 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 19 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 20 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 21 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 22 |
Correct |
0 ms |
6972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6972 KB |
Output is correct |
| 2 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 3 |
Correct |
16 ms |
6972 KB |
Output is correct |
| 4 |
Correct |
20 ms |
6972 KB |
Output is correct |
| 5 |
Correct |
20 ms |
6972 KB |
Output is correct |
| 6 |
Correct |
32 ms |
6972 KB |
Output is correct |
| 7 |
Correct |
28 ms |
6972 KB |
Output is correct |
| 8 |
Correct |
20 ms |
6972 KB |
Output is correct |
| 9 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 10 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 11 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 12 |
Correct |
24 ms |
6972 KB |
Output is correct |
| 13 |
Correct |
24 ms |
6972 KB |
Output is correct |
| 14 |
Correct |
24 ms |
6972 KB |
Output is correct |
| 15 |
Correct |
8 ms |
6972 KB |
Output is correct |
| 16 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 17 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 18 |
Correct |
4 ms |
6972 KB |
Output is correct |
| 19 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 20 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 21 |
Correct |
0 ms |
6972 KB |
Output is correct |
| 22 |
Correct |
0 ms |
6972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
6972 KB |
Output is correct |
| 2 |
Correct |
52 ms |
6972 KB |
Output is correct |
| 3 |
Correct |
80 ms |
6972 KB |
Output is correct |
| 4 |
Correct |
60 ms |
6972 KB |
Output is correct |
| 5 |
Correct |
56 ms |
6972 KB |
Output is correct |
| 6 |
Correct |
84 ms |
6972 KB |
Output is correct |
| 7 |
Correct |
52 ms |
6972 KB |
Output is correct |
| 8 |
Correct |
48 ms |
6972 KB |
Output is correct |
| 9 |
Correct |
36 ms |
6972 KB |
Output is correct |
| 10 |
Correct |
44 ms |
6972 KB |
Output is correct |
| 11 |
Correct |
48 ms |
6972 KB |
Output is correct |
| 12 |
Correct |
72 ms |
6972 KB |
Output is correct |
| 13 |
Correct |
64 ms |
6972 KB |
Output is correct |
| 14 |
Correct |
64 ms |
6972 KB |
Output is correct |
| 15 |
Correct |
36 ms |
6972 KB |
Output is correct |
| 16 |
Correct |
40 ms |
6972 KB |
Output is correct |
| 17 |
Correct |
28 ms |
6972 KB |
Output is correct |
| 18 |
Correct |
20 ms |
6972 KB |
Output is correct |
| 19 |
Correct |
20 ms |
6972 KB |
Output is correct |
| 20 |
Correct |
16 ms |
6972 KB |
Output is correct |
| 21 |
Correct |
12 ms |
6972 KB |
Output is correct |
| 22 |
Correct |
16 ms |
6972 KB |
Output is correct |
