oj.uz

Submission #2872

# Submission time Handle Problem Language Result Execution time Memory
2872 2013-08-01T06:31:17 Z ladown21 간선 파괴 (GA5_destroy) C++
25 / 100
 2500 ms 3400 KB 
#include <stdio.h>
#include <algorithm>

struct Edge{int a,b,i;}G[130000],q[50010];
Edge inner(int a,int b, int i)
{Edge r={a,b,i};return r;}

int T[800],ans[50010];

int ufind(int k)
{return T[k]=(T[k]==k)?k:ufind(T[k]);}

bool cmp_a(Edge a, Edge b)
{return ((a.a==b.a)?a.b>b.b:a.a<b.a);}
bool cmp_i(Edge a, Edge b)
{return a.i<b.i;}

int Cnt(int V)
{
	int C[800]={0}, ret=0;
	for (int i=1; i<=V; i++)
		ret += (C[T[i]]++)==0;
	return ret;
}

int main()
{
	int V,E,Q;
	scanf("%d%d",&V,&E);

	int u,v;
	for (int i=1; i<=E; i++) {
		scanf("%d%d",&u,&v);
		if (u>v) u^=v,v^=u,u^=v;
		G[i] = inner(u,v,i);
	}

	scanf("%d",&Q);
	for (int i=1; i<=Q; i++) {
		scanf("%d%d",&u,&v);
		q[i] = inner(u,v,i);
	}
	std::sort(q+1,q+1+Q, cmp_a);

	
	int a=0,b=E;
	for (int i=1; i<=Q; i++) {
		if (a!=q[i].a) {
			for (int i=1; i<=V; i++) T[i] = i;
			a=0;
			b=E;
		}

		for (int k=1; k<q[i].a; k++)
			T[ufind(G[k].a)] = ufind(G[k].b);
		for (int k=b; k>q[i].b; k--)
			T[ufind(G[k].a)] = ufind(G[k].b);
		for (int k=1; k<=V; k++) ufind(k);

		ans[q[i].i] = Cnt(V);
		a=q[i].a;
		b=q[i].b;
	}
	for (int i=1; i<=Q; i++)
		printf("%d\n",ans[i]);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3400 KB Output is correct
2 Correct 0 ms 3400 KB Output is correct
3 Correct 0 ms 3400 KB Output is correct
4 Correct 0 ms 3400 KB Output is correct
5 Correct 0 ms 3400 KB Output is correct
6 Correct 0 ms 3400 KB Output is correct
7 Correct 0 ms 3400 KB Output is correct
8 Correct 0 ms 3400 KB Output is correct
9 Correct 0 ms 3400 KB Output is correct
10 Correct 0 ms 3400 KB Output is correct
11 Correct 0 ms 3400 KB Output is correct
12 Correct 0 ms 3400 KB Output is correct
13 Correct 0 ms 3400 KB Output is correct
14 Correct 0 ms 3400 KB Output is correct
15 Correct 0 ms 3400 KB Output is correct
16 Correct 0 ms 3400 KB Output is correct
17 Correct 0 ms 3400 KB Output is correct
18 Correct 0 ms 3400 KB Output is correct
19 Correct 0 ms 3400 KB Output is correct
20 Correct 0 ms 3400 KB Output is correct
21 Correct 0 ms 3400 KB Output is correct
22 Correct 0 ms 3400 KB Output is correct

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 3400 KB Output is correct
2 Correct 288 ms 3400 KB Output is correct
3 Correct 352 ms 3400 KB Output is correct
4 Correct 932 ms 3400 KB Output is correct
5 Correct 1096 ms 3400 KB Output is correct
6 Execution timed out 2500 ms 3396 KB Program timed out
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2500 ms 3396 KB Program timed out
2 Halted 0 ms 0 KB -