Submission #742586

#	Time	Username	Problem	Language	Result	Execution time	Memory
742586		flappybird	전압 (JOI14_voltage)	C++17	100 / 100	191 ms	31728 KiB

voltage

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> edges;
vector<int> adj[MAX], tree[MAX];
int col[MAX];
int dep[MAX];
int find_nxt(int x, int e) {
	return edges[e].first + edges[e].second - x;
}
int vis[MAX];
int istree[MAX];
int isroot[MAX];
void dfs(int x, int p = 0) {
	if (!p) isroot[x] = 1;
	vis[x] = 1;
	for (auto e : adj[x]) {
		if (p == e) continue;
		int v = find_nxt(x, e);
		if (vis[v]) continue;
		tree[x].push_back(v);
		istree[e] = 1;
		col[v] = col[x] ^ 1;
		dep[v] = dep[x] + 1;
		dfs(v, e);
	}
}
int ban[MAX];
int need[MAX];
void calc(int x) { vis[x] = 1; for (auto v : tree[x]) calc(v), ban[x] += ban[v], need[x] += need[v]; }
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M;
	cin >> N >> M;
	int i, a, b;
	edges.emplace_back(0, 0);
	for (i = 1; i <= M; i++) {
		cin >> a >> b;
		edges.emplace_back(a, b);
		adj[a].push_back(i);
		adj[b].push_back(i);
	}
	for (i = 1; i <= N; i++) if (!vis[i]) dfs(i);
	memset(vis, 0, sizeof(vis));
	int c = 0;
	for (i = 1; i <= M; i++) {
		if (col[edges[i].first] ^ col[edges[i].second]) continue;
		c++;
	}
	int ans = 0;
	if (c == 1) ans = 1;
	int ncnt = 0;
	for (i = 1; i <= M; i++) if (!istree[i]) {
		auto& [a, b] = edges[i];
		if (dep[a] > dep[b]) swap(a, b);
		if (col[a] ^ col[b]) {
			ban[b]++;
			ban[a]--;
		}
		else {
			need[b]++;
			need[a]--;
			ncnt++;
		}
	}
	for (i = 1; i <= N; i++) if (!vis[i]) calc(i);
	for (i = 1; i <= N; i++) if (!isroot[i] && !ban[i] && need[i] == ncnt) ans++;
	cout << ans << ln;
}

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