oj.uz

답안 #469867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469867 2021-09-02T07:40:39 Z 1bin 산만한 고양이 (KOI17_cat) C++14
33 / 100
 280 ms 59000 KB 
#include <bits/stdc++.h>
#include <cassert>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
ll n, m, a, b, dfsn[NMAX], cnt[NMAX], y[NMAX], t, ans, sum, tmp[NMAX];
vector<int> adj[NMAX];

void dfs(int now, int bef) {
	dfsn[now] = ++t;
	ll x = 0;

	for (int nx : adj[now]) {
		if (nx == bef) continue;
		if (!dfsn[nx]) {
			dfs(nx, now);
			cnt[now] += cnt[nx]; y[now] += y[nx];
			tmp[now] += tmp[nx];
		}
		else if (dfsn[nx] < dfsn[now]) x++, cnt[bef]++, tmp[now]++;
		else x++, cnt[now]--, y[bef]++;
	}
	assert(tmp[now] == x + y[now] + cnt[now]);
	if (!y[now] && cnt[now] <= 1 && !(sum - x - y[now] - cnt[now])) ans += now;
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	sum = m - (n - 1);
	while (m--) {
		cin >> a >> b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	dfs(1, 0);
	cout << ans;
	return 0;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 26460 KB Output is correct
2 Correct 230 ms 26336 KB Output is correct
3 Correct 227 ms 26460 KB Output is correct
4 Correct 244 ms 26460 KB Output is correct
5 Correct 238 ms 26500 KB Output is correct
6 Correct 226 ms 26580 KB Output is correct
7 Correct 222 ms 26460 KB Output is correct
8 Correct 236 ms 26616 KB Output is correct
9 Correct 240 ms 26556 KB Output is correct
10 Correct 250 ms 26484 KB Output is correct
11 Correct 256 ms 27160 KB Output is correct
12 Correct 232 ms 27256 KB Output is correct
13 Correct 280 ms 27076 KB Output is correct
14 Correct 257 ms 27260 KB Output is correct
15 Correct 252 ms 27284 KB Output is correct
16 Correct 228 ms 33508 KB Output is correct
17 Correct 230 ms 35164 KB Output is correct
18 Correct 270 ms 32120 KB Output is correct
19 Correct 225 ms 33732 KB Output is correct
20 Correct 242 ms 32284 KB Output is correct
21 Correct 242 ms 29828 KB Output is correct
22 Correct 243 ms 42284 KB Output is correct
23 Correct 219 ms 46148 KB Output is correct
24 Correct 262 ms 30288 KB Output is correct
25 Correct 220 ms 44696 KB Output is correct
26 Correct 119 ms 58992 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 58952 KB Output is correct
2 Correct 121 ms 58996 KB Output is correct
3 Correct 120 ms 59000 KB Output is correct
4 Correct 122 ms 58904 KB Output is correct
5 Correct 120 ms 58896 KB Output is correct
6 Correct 126 ms 58932 KB Output is correct
7 Correct 124 ms 58928 KB Output is correct
8 Correct 120 ms 58968 KB Output is correct
9 Correct 121 ms 58904 KB Output is correct
10 Correct 132 ms 50636 KB Output is correct
11 Correct 129 ms 50684 KB Output is correct
12 Correct 130 ms 50712 KB Output is correct
13 Correct 135 ms 50656 KB Output is correct
14 Correct 134 ms 50636 KB Output is correct
15 Correct 142 ms 42304 KB Output is correct
16 Correct 139 ms 42224 KB Output is correct
17 Correct 141 ms 42220 KB Output is correct
18 Correct 132 ms 42220 KB Output is correct
19 Correct 134 ms 42320 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7392 KB Output isn't correct
2 Halted 0 ms 0 KB -