oj.uz

Submission #16534

# Submission time Handle Problem Language Result Execution time Memory
16534 2015-08-27T08:17:01 Z Qwaz 전압 (JOI14_voltage) C++14
100 / 100
 191 ms 29380 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 200020;

typedef pair < int, int > pii;

vector < pii > to[MAX];
vector < int > root, child[MAX];
int depth[MAX];

int numNode, numEdge;

void input() {
	scanf("%d%d", &numNode, &numEdge);

	int i;
	for (i = 0; i < numEdge; i++) {
		int f, s;
		scanf("%d%d", &f, &s);
		to[f].push_back(pii(s, i));
		to[s].push_back(pii(f, i));
	}
}

int parent[MAX], state, numOddCycle, evenCount[MAX], oddCount[MAX];

void initDFS(int node) {
	root.push_back(node);
	parent[node] = node;
	depth[node] = 1;
	state = 0;
	numOddCycle = 0;
}

bool used[MAX];

void dfs(int node) {
	for (int edge = 0; edge < to[node].size(); edge++) {
		bool &visited = used[to[node][edge].second];
		if (visited) continue;
		visited = 1;

		int next = to[node][edge].first;
		if (depth[next] == 0) {
			parent[next] = node;
			depth[next] = depth[node]+1;
			child[node].push_back(next);
			dfs(next);
		} else {
			if ((depth[node]-depth[next])&1) {
				//even cycle
				evenCount[node]++;
				evenCount[next]--;
			} else {
				//odd cycle
				if (state == 0) state = 1;
				else if (state == 1) state = 2;
				numOddCycle++;
				oddCount[node]++;
				oddCount[next]--;
			}
		}
	}
}

int countDFS(int node) {
	int ret = 0;
	for (int edge = 0; edge < child[node].size(); edge++) {
		int next = child[node][edge];
		ret += countDFS(next);
		evenCount[node] += evenCount[next];
		oddCount[node] += oddCount[next];
	}
	
	if (evenCount[node] == 0 && oddCount[node] == numOddCycle && parent[node] != node) ret++;

	return ret;
}

int ans = 0;
bool oddCycleExist = 0;

void solve() {
	for (int node = 1; node <= numNode; node++) {
		if (parent[node] == 0) {
			initDFS(node);
			dfs(node);
			int waiting = countDFS(node);
			if (state == 1) {
				//only one odd cycle
				waiting++;
			}

			if (!oddCycleExist) {
				if (state > 0) {
					ans = waiting;
					oddCycleExist = 1;
				} else {
					ans += waiting;
				}
			} else {
				if (state > 0) {
					ans = 0;
					break;
				}
			}
		}
	}

	printf("%d\n", ans);
}

int main() {
	input();

	solve();

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 19088 KB Output is correct
2 Correct 106 ms 24500 KB Output is correct
3 Correct 39 ms 19088 KB Output is correct
4 Correct 91 ms 26112 KB Output is correct
5 Correct 12 ms 14572 KB Output is correct
6 Correct 85 ms 21720 KB Output is correct
7 Correct 97 ms 27804 KB Output is correct
8 Correct 67 ms 27796 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 19088 KB Output is correct
2 Correct 57 ms 27796 KB Output is correct
3 Correct 48 ms 27796 KB Output is correct
4 Correct 0 ms 13908 KB Output is correct
5 Correct 52 ms 22288 KB Output is correct
6 Correct 78 ms 19188 KB Output is correct
7 Correct 74 ms 23116 KB Output is correct
8 Correct 108 ms 25220 KB Output is correct
9 Correct 60 ms 24456 KB Output is correct
10 Correct 91 ms 22784 KB Output is correct
11 Correct 65 ms 19188 KB Output is correct
12 Correct 83 ms 21600 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 20112 KB Output is correct
2 Correct 123 ms 29380 KB Output is correct
3 Correct 7 ms 14680 KB Output is correct
4 Correct 122 ms 24176 KB Output is correct
5 Correct 108 ms 25464 KB Output is correct
6 Correct 86 ms 23848 KB Output is correct
7 Correct 149 ms 25388 KB Output is correct
8 Correct 191 ms 26608 KB Output is correct
9 Correct 160 ms 23960 KB Output is correct
10 Correct 168 ms 26992 KB Output is correct
11 Correct 171 ms 23740 KB Output is correct
12 Correct 146 ms 27020 KB Output is correct
13 Correct 120 ms 23652 KB Output is correct
14 Correct 143 ms 27828 KB Output is correct
15 Correct 177 ms 27064 KB Output is correct
16 Correct 154 ms 26432 KB Output is correct
17 Correct 123 ms 24060 KB Output is correct
18 Correct 100 ms 24656 KB Output is correct