oj.uz

답안 #469866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469866 2021-09-02T07:36:08 Z 1bin 산만한 고양이 (KOI17_cat) C++14
33 / 100
 264 ms 52036 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;
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];
		}
		else if (dfsn[nx] < dfsn[now]) x++, cnt[bef]++;
		else x++, cnt[now]--, y[bef]++;
	}
	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 5 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 24212 KB Output is correct
2 Correct 245 ms 24092 KB Output is correct
3 Correct 237 ms 24108 KB Output is correct
4 Correct 223 ms 24080 KB Output is correct
5 Correct 264 ms 24008 KB Output is correct
6 Correct 232 ms 24192 KB Output is correct
7 Correct 248 ms 24052 KB Output is correct
8 Correct 235 ms 24124 KB Output is correct
9 Correct 235 ms 24228 KB Output is correct
10 Correct 230 ms 24148 KB Output is correct
11 Correct 223 ms 24776 KB Output is correct
12 Correct 233 ms 24788 KB Output is correct
13 Correct 246 ms 24644 KB Output is correct
14 Correct 241 ms 24772 KB Output is correct
15 Correct 230 ms 24732 KB Output is correct
16 Correct 219 ms 30124 KB Output is correct
17 Correct 239 ms 31576 KB Output is correct
18 Correct 222 ms 28996 KB Output is correct
19 Correct 223 ms 30228 KB Output is correct
20 Correct 237 ms 29020 KB Output is correct
21 Correct 227 ms 27080 KB Output is correct
22 Correct 216 ms 37560 KB Output is correct
23 Correct 198 ms 40992 KB Output is correct
24 Correct 224 ms 27620 KB Output is correct
25 Correct 204 ms 39656 KB Output is correct
26 Correct 129 ms 51864 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 52036 KB Output is correct
2 Correct 119 ms 51916 KB Output is correct
3 Correct 142 ms 51916 KB Output is correct
4 Correct 117 ms 52036 KB Output is correct
5 Correct 116 ms 51896 KB Output is correct
6 Correct 130 ms 51936 KB Output is correct
7 Correct 117 ms 51908 KB Output is correct
8 Correct 118 ms 51852 KB Output is correct
9 Correct 116 ms 51912 KB Output is correct
10 Correct 134 ms 44776 KB Output is correct
11 Correct 127 ms 44776 KB Output is correct
12 Correct 128 ms 44784 KB Output is correct
13 Correct 129 ms 44736 KB Output is correct
14 Correct 138 ms 44764 KB Output is correct
15 Correct 148 ms 37568 KB Output is correct
16 Correct 133 ms 37508 KB Output is correct
17 Correct 137 ms 37504 KB Output is correct
18 Correct 134 ms 37536 KB Output is correct
19 Correct 137 ms 37528 KB Output is correct

Subtask #4
0 / 55.0

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