oj.uz

Submission #6010

# Submission time Handle Problem Language Result Execution time Memory
6010 2014-06-14T13:46:54 Z ainta 전압 (JOI14_voltage) C++
100 / 100
 144 ms 13520 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct A{
	int a, b;
}tp;
vector<A>E[100010];
int n, m, Dep[100010], par[100010], S, D[100010], Res, ord[100010], cnt;
bool v[100010], chk[200010];
void DFS(int a)
{
	ord[++cnt] = a;
	int i;
	Dep[a] = Dep[par[a]] + 1;
	v[a] = true;
	for (i = 0; i < E[a].size(); i++){
		if (!v[E[a][i].a]){
			chk[E[a][i].b] = true;
			par[E[a][i].a] = a;
			DFS(E[a][i].a);
		}
	}
}
int main()
{
	int i, a, b, j, ck;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++){
		scanf("%d%d", &a, &b);
		tp.a = b, tp.b = i;
		E[a].push_back(tp);
		tp.a = a;
		E[b].push_back(tp);
	}
	for (i = 1; i <= n; i++){
		if (!v[i]){
			DFS(i);
		}
	}
	for (i = 1; i <= n; i++){
		for (j = 0; j < E[i].size(); j++){
			if (!chk[E[i][j].b]){
				chk[E[i][j].b] = true;
				ck = -1;
				if ((Dep[i] + Dep[E[i][j].a]) % 2 == 0){
					S++;
					ck = 1;
				}
				a = E[i][j].a, b = i;
				if (Dep[i] > Dep[E[i][j].a])swap(a, b);
				D[a] += ck, D[b] += -ck;
			}
		}
	}
	if (S == 1)Res++;
	for (i = cnt; i >= 1; i--){
		a = ord[i];
		D[par[a]] += D[a];
		if (D[a] == S && par[a]){
			Res++;
		}
	}
	printf("%d\n", Res);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5404 KB Output is correct
2 Correct 0 ms 5404 KB Output is correct
3 Correct 0 ms 5404 KB Output is correct
4 Correct 0 ms 5404 KB Output is correct
5 Correct 0 ms 5404 KB Output is correct
6 Correct 0 ms 5404 KB Output is correct
7 Correct 0 ms 5404 KB Output is correct
8 Correct 0 ms 5404 KB Output is correct
9 Correct 0 ms 5404 KB Output is correct
10 Correct 0 ms 5404 KB Output is correct
11 Correct 0 ms 5404 KB Output is correct
12 Correct 0 ms 5404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9468 KB Output is correct
2 Correct 64 ms 10116 KB Output is correct
3 Correct 40 ms 9468 KB Output is correct
4 Correct 60 ms 10768 KB Output is correct
5 Correct 8 ms 5800 KB Output is correct
6 Correct 56 ms 9856 KB Output is correct
7 Correct 56 ms 11440 KB Output is correct
8 Correct 76 ms 11444 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9468 KB Output is correct
2 Correct 40 ms 11440 KB Output is correct
3 Correct 44 ms 11436 KB Output is correct
4 Correct 0 ms 5404 KB Output is correct
5 Correct 52 ms 9600 KB Output is correct
6 Correct 64 ms 9100 KB Output is correct
7 Correct 60 ms 10120 KB Output is correct
8 Correct 60 ms 10412 KB Output is correct
9 Correct 68 ms 10660 KB Output is correct
10 Correct 64 ms 9992 KB Output is correct
11 Correct 60 ms 9100 KB Output is correct
12 Correct 72 ms 9516 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11516 KB Output is correct
2 Correct 72 ms 13028 KB Output is correct
3 Correct 4 ms 5404 KB Output is correct
4 Correct 76 ms 10708 KB Output is correct
5 Correct 76 ms 11220 KB Output is correct
6 Correct 84 ms 10624 KB Output is correct
7 Correct 144 ms 12852 KB Output is correct
8 Correct 128 ms 12756 KB Output is correct
9 Correct 120 ms 12120 KB Output is correct
10 Correct 140 ms 13360 KB Output is correct
11 Correct 124 ms 11992 KB Output is correct
12 Correct 136 ms 13504 KB Output is correct
13 Correct 116 ms 12316 KB Output is correct
14 Correct 132 ms 13428 KB Output is correct
15 Correct 132 ms 13520 KB Output is correct
16 Correct 124 ms 12980 KB Output is correct
17 Correct 120 ms 11992 KB Output is correct
18 Correct 96 ms 12480 KB Output is correct