oj.uz

Submission #742586

# Submission time Handle Problem Language Result Execution time Memory
742586 2023-05-16T14:17:02 Z flappybird 전압 (JOI14_voltage) C++17
100 / 100
 191 ms 31728 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 6 ms 10540 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 6 ms 10748 KB Output is correct
6 Correct 6 ms 10708 KB Output is correct
7 Correct 6 ms 10772 KB Output is correct
8 Correct 7 ms 10752 KB Output is correct
9 Correct 6 ms 10708 KB Output is correct
10 Correct 7 ms 10708 KB Output is correct
11 Correct 7 ms 10684 KB Output is correct
12 Correct 7 ms 10708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16952 KB Output is correct
2 Correct 87 ms 25824 KB Output is correct
3 Correct 43 ms 16900 KB Output is correct
4 Correct 96 ms 28140 KB Output is correct
5 Correct 10 ms 11796 KB Output is correct
6 Correct 83 ms 21752 KB Output is correct
7 Correct 94 ms 30488 KB Output is correct
8 Correct 87 ms 30488 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16888 KB Output is correct
2 Correct 46 ms 30512 KB Output is correct
3 Correct 53 ms 30404 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 62 ms 22656 KB Output is correct
6 Correct 74 ms 18040 KB Output is correct
7 Correct 73 ms 23740 KB Output is correct
8 Correct 81 ms 26904 KB Output is correct
9 Correct 76 ms 25640 KB Output is correct
10 Correct 73 ms 23312 KB Output is correct
11 Correct 80 ms 18208 KB Output is correct
12 Correct 92 ms 21676 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18492 KB Output is correct
2 Correct 66 ms 31192 KB Output is correct
3 Correct 7 ms 10964 KB Output is correct
4 Correct 84 ms 26240 KB Output is correct
5 Correct 83 ms 28144 KB Output is correct
6 Correct 88 ms 25916 KB Output is correct
7 Correct 152 ms 28032 KB Output is correct
8 Correct 137 ms 29856 KB Output is correct
9 Correct 138 ms 26132 KB Output is correct
10 Correct 191 ms 30204 KB Output is correct
11 Correct 146 ms 26168 KB Output is correct
12 Correct 135 ms 30136 KB Output is correct
13 Correct 120 ms 25192 KB Output is correct
14 Correct 147 ms 31728 KB Output is correct
15 Correct 167 ms 30520 KB Output is correct
16 Correct 126 ms 29752 KB Output is correct
17 Correct 126 ms 26252 KB Output is correct
18 Correct 90 ms 26172 KB Output is correct