oj.uz

답안 #332168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332168 2020-12-01T15:13:40 Z oolimry 산만한 고양이 (KOI17_cat) C++14
23 / 100
 266 ms 45036 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300005];
int root = 1;
int rootChild = 0;
int parts[300005];
int low[300005];
int depth[300005];
int p[300005];

void tarjan(int u){
	low[u] = depth[u];
	for(int v : adj[u]){
		if(depth[v] == 0){
			depth[v] = depth[u] + 1;
			if(u == root) rootChild++; 
			
			p[v] = u;
			tarjan(v);
			
			if(low[v] > depth[u]) parts[u]++;
			low[u] = min(low[u], low[v]);
		}
		if(depth[v] < depth[u] - 1){
			low[u] = min(low[u], depth[v]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	
	for(int i = 0;i < m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		assert(a != b);
	}
	
	depth[root] = 1;
	tarjan(root);
	for(int i = 1;i <= n;i++) parts[i]++;
	parts[root] = rootChild;

	
	long long ans = 0;
	for(int i = 1;i <= n;i++){
		int target = (n - 1) - parts[i];
		int leftEdges = m - (int) adj[i].size();
		
		if(target == leftEdges){
			ans += i;
		}
	}
	
	cout << ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 44908 KB Output is correct
2 Correct 120 ms 44908 KB Output is correct
3 Correct 111 ms 44908 KB Output is correct
4 Correct 127 ms 44988 KB Output is correct
5 Correct 112 ms 44908 KB Output is correct
6 Correct 122 ms 44908 KB Output is correct
7 Correct 113 ms 44908 KB Output is correct
8 Correct 122 ms 44908 KB Output is correct
9 Correct 110 ms 45036 KB Output is correct
10 Correct 133 ms 39024 KB Output is correct
11 Correct 132 ms 39024 KB Output is correct
12 Correct 130 ms 39152 KB Output is correct
13 Correct 136 ms 39024 KB Output is correct
14 Correct 132 ms 39024 KB Output is correct
15 Correct 139 ms 32916 KB Output is correct
16 Correct 142 ms 32996 KB Output is correct
17 Correct 162 ms 32996 KB Output is correct
18 Correct 143 ms 32996 KB Output is correct
19 Correct 141 ms 32996 KB Output is correct

Subtask #4
0 / 55.0

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