Submission #16464

#	Time	Username	Problem	Language	Result	Execution time	Memory
16464		kaTkaHr	전압 (JOI14_voltage)	C++14	100 / 100	229 ms	35956 KiB

voltage

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