Submission #16534

#	Time	Username	Problem	Language	Result	Execution time	Memory
16534		Qwaz	전압 (JOI14_voltage)	C++14	100 / 100	191 ms	29380 KiB

voltage

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45