oj.uz

Submission #16464

# Submission time Handle Problem Language Result Execution time Memory
16464 2015-08-25T23:35:26 Z kaTkaHr 전압 (JOI14_voltage) C++14
100 / 100
 229 ms 35956 KB 
#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> pii;

const int MX = 100005;

vector<pii> G[MX], B;
vector<int> T[MX];

int C[MX], P[20][MX], lev[MX];
int cnt, ans, cut[MX], con[MX];

void dfs(int x, int p)
{
	for (pii cc : G[x]){
		int &c = cc.first, &d = cc.second;
		if (d == p) continue;
		if (C[c] && x > c)B.push_back(pii(x, c));
		else if( !C[c] ){
			T[x].push_back(c);
			P[0][c] = x; lev[c] = lev[x] + 1;
			C[c] = 3 - C[x];
			dfs(c, d);
		}
	}
}

pii solve(int x)
{
	if (C[x] == 3) return pii(0, 0);
	C[x] = 3;
	pii tot = pii(cut[x], con[x]);
	for (int c : T[x]){
		pii t = solve(c);
		tot.first += t.first;
		tot.second += t.second;
	}
	if (tot.first == cnt && tot.second == 0) ans++;
	return tot;
}

void up(int &x, int d)
{
	if (d < 0) return;
	for (int i = 0; d; i++, d /= 2){
		if (d & 1) x = P[i][x];
	}
}

int LCA(int A, int B)
{
	up(A, lev[A] - lev[B]);
	up(B, lev[B] - lev[A]);
	for (int i = 0; i < 20; i++){
		if (P[i][A] != P[i][B]) A = P[i][A], B = P[i][B];
	}
	if (A != B) return P[0][A];
	else return A;
}

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++){
		int X, Y;
		scanf("%d%d", &X, &Y);
		if (X == Y) for (;;);
		G[X].push_back(pii(Y, i));
		G[Y].push_back(pii(X, i));
	}
	for (int i = 1; i <= N; i++){
		if (C[i]) continue;
		C[i] = 1; lev[i] = 1;
		dfs(i, -1);
	}
	for (int i = 1; i < 20; i++){
		for (int j = 1; j <= N; j++){
			P[i][j] = P[i - 1][P[i - 1][j]];
		}
	}

	for (pii c : B){
		int X = c.first, Y = c.second;
		int p = LCA(X, Y);
		if (C[X] == C[Y]){
			cnt++;
			cut[X]++, cut[Y]++, cut[p] -= 2;
		}
		else{
			con[X]++, con[Y]++, con[p] -= 2;
		}
	}
	if (cnt == 1) ans++;
	for (int i = 1; i <= N; i++){
		if (C[i] == 3) continue;
		solve(i);
		if (cnt == 0) ans--; // root
	}
	printf("%d", ans);
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 20964 KB Output is correct
2 Correct 96 ms 28176 KB Output is correct
3 Correct 57 ms 20964 KB Output is correct
4 Correct 91 ms 30440 KB Output is correct
5 Correct 3 ms 16552 KB Output is correct
6 Correct 85 ms 24604 KB Output is correct
7 Correct 95 ms 32800 KB Output is correct
8 Correct 57 ms 32804 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 20964 KB Output is correct
2 Correct 66 ms 32800 KB Output is correct
3 Correct 71 ms 32804 KB Output is correct
4 Correct 0 ms 15784 KB Output is correct
5 Correct 59 ms 25720 KB Output is correct
6 Correct 71 ms 21064 KB Output is correct
7 Correct 100 ms 26400 KB Output is correct
8 Correct 88 ms 29192 KB Output is correct
9 Correct 82 ms 28288 KB Output is correct
10 Correct 83 ms 25936 KB Output is correct
11 Correct 62 ms 21064 KB Output is correct
12 Correct 81 ms 24276 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 23012 KB Output is correct
2 Correct 95 ms 35956 KB Output is correct
3 Correct 7 ms 15784 KB Output is correct
4 Correct 91 ms 27916 KB Output is correct
5 Correct 92 ms 29652 KB Output is correct
6 Correct 96 ms 27640 KB Output is correct
7 Correct 158 ms 30220 KB Output is correct
8 Correct 215 ms 31708 KB Output is correct
9 Correct 190 ms 28272 KB Output is correct
10 Correct 223 ms 32416 KB Output is correct
11 Correct 195 ms 28176 KB Output is correct
12 Correct 229 ms 32484 KB Output is correct
13 Correct 163 ms 27348 KB Output is correct
14 Correct 200 ms 33588 KB Output is correct
15 Correct 203 ms 32532 KB Output is correct
16 Correct 184 ms 32004 KB Output is correct
17 Correct 208 ms 29776 KB Output is correct
18 Correct 134 ms 30488 KB Output is correct