Submission #221437

#	Time	Username	Problem	Language	Result	Execution time	Memory
221437		bensonlzl	전압 (JOI14_voltage)	C++14	100 / 100	160 ms	19192 KiB

voltage

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

vector<pi> AdjList[100005];
int colour[100005], visit[100005], depth[100005];
int badup[100005], goodup[100005];
int badlow[100005], goodlow[100005];
int badlep[100005], goodlep[100005];
int baduep[100005], gooduep[100005];
int par[100005];
int N, M, A, B;
int total_bad = 0;
int usable = 0;

void dfs(int x, int p){
	par[x] = p;
	//cout << x << ' ' << p << '\n';
	visit[x] = 1;
	for (auto it : AdjList[x]){
		int v = it.first, e = it.second;
		if (e == p) continue;
		if (visit[v]){
			if (depth[x] > depth[v]){
				if (colour[x] == colour[v]){
					badlep[x]++;
					badup[x]++;
					baduep[v]++;
					total_bad++;
				}
				else{
					goodlep[x]++;
					goodup[x]++;
					gooduep[v]++;
				}
			}
		}
		else{
			depth[v] = depth[x] + 1;
			colour[v] = 1 - colour[x];
			dfs(v,e);
			badup[x] += badup[v];
			goodup[x] += goodup[v];
		}
	}
	badup[x] -= baduep[x];
	goodup[x] -= gooduep[x];
}

void check_vertex(int x, int p){
	visit[x] = 1;
	//cout << "CHECKING " << x << ' ' << p << '\n';
	if (p != -1){
		if (total_bad == badup[x]){
			if (goodup[x] == 0){
				usable++;
				//cout << p << " CASE 1A\n";
			}
		}
	}
	for (auto it : AdjList[x]){
		int v = it.first, e = it.second;
		if (p == e) continue;
		if (par[v] == e){
			check_vertex(v,e);
		}
		else{
			if (depth[x] < depth[v]) continue;
			if (total_bad == 1 && colour[v] == colour[x]){
				usable++;
				//cout << "CASE 2A\n";
			}
		}
	}
	//cout << "ENDING " << x << ' ' << p << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i){
		cin >> A >> B;
		AdjList[A].push_back(pi(B,i));
		AdjList[B].push_back(pi(A,i));
	}
	for (int i = 1; i <= N; ++i){
		if (!visit[i]){
			depth[i] = 0;
			colour[i] = 0;
			dfs(i,-1);
		} 
	}
	for (int i = 1; i <= N; ++i){
		visit[i] = 0;
	}
	for (int i = 1; i <= N; ++i){
		if (!visit[i]){
			check_vertex(i,-1);
		} 
	}
	/*
	for (int i = 1; i <= N; ++i){
		cout << badup[i] << ' ' << goodup[i] << '\n';
	}
	*/
	cout << usable << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45