oj.uz

답안 #332160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332160 2020-12-01T15:04:02 Z oolimry 산만한 고양이 (KOI17_cat) C++14
23 / 100
 263 ms 49004 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(v != p[u]){
			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 = 2;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 7 ms 7404 KB Output is correct
2 Correct 7 ms 7404 KB Output is correct
3 Incorrect 6 ms 7404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 48892 KB Output is correct
2 Correct 124 ms 48896 KB Output is correct
3 Correct 142 ms 49004 KB Output is correct
4 Correct 119 ms 48876 KB Output is correct
5 Correct 118 ms 48876 KB Output is correct
6 Correct 115 ms 48876 KB Output is correct
7 Correct 129 ms 48876 KB Output is correct
8 Correct 120 ms 48876 KB Output is correct
9 Correct 115 ms 48876 KB Output is correct
10 Correct 132 ms 42864 KB Output is correct
11 Correct 137 ms 42864 KB Output is correct
12 Correct 131 ms 42864 KB Output is correct
13 Correct 135 ms 42864 KB Output is correct
14 Correct 162 ms 42864 KB Output is correct
15 Correct 147 ms 36836 KB Output is correct
16 Correct 150 ms 36708 KB Output is correct
17 Correct 155 ms 36836 KB Output is correct
18 Correct 147 ms 36708 KB Output is correct
19 Correct 144 ms 36836 KB Output is correct

Subtask #4
0 / 55.0

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