oj.uz

Submission #742585

# Submission time Handle Problem Language Result Execution time Memory
742585 2023-05-16T14:12:52 Z flappybird 전압 (JOI14_voltage) C++17
45 / 100
 94 ms 33592 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];
void dfs(int x, int p = 0) {
	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 = 2; i <= N; i++) if (!ban[i] && need[i] == ncnt) ans++;
	cout << ans << ln;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Incorrect 6 ms 10580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18112 KB Output is correct
2 Correct 82 ms 26932 KB Output is correct
3 Correct 47 ms 18112 KB Output is correct
4 Correct 92 ms 29196 KB Output is correct
5 Correct 14 ms 11860 KB Output is correct
6 Correct 75 ms 22844 KB Output is correct
7 Correct 79 ms 31600 KB Output is correct
8 Correct 85 ms 31768 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17736 KB Output is correct
2 Correct 41 ms 31604 KB Output is correct
3 Correct 43 ms 31644 KB Output is correct
4 Correct 6 ms 10580 KB Output is correct
5 Correct 56 ms 23484 KB Output is correct
6 Correct 68 ms 19224 KB Output is correct
7 Correct 78 ms 24964 KB Output is correct
8 Correct 86 ms 27932 KB Output is correct
9 Correct 81 ms 26840 KB Output is correct
10 Correct 94 ms 24384 KB Output is correct
11 Correct 62 ms 19352 KB Output is correct
12 Correct 81 ms 22848 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 19952 KB Output is correct
2 Correct 64 ms 33592 KB Output is correct
3 Incorrect 7 ms 10580 KB Output isn't correct
4 Halted 0 ms 0 KB -