oj.uz

답안 #332154

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332154 2020-12-01T15:00:14 Z oolimry 산만한 고양이 (KOI17_cat) C++14
23 / 100
 260 ms 49072 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);
	}
	
	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 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Incorrect 5 ms 7552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 49072 KB Output is correct
2 Correct 115 ms 48992 KB Output is correct
3 Correct 115 ms 48876 KB Output is correct
4 Correct 126 ms 48876 KB Output is correct
5 Correct 117 ms 48876 KB Output is correct
6 Correct 118 ms 48848 KB Output is correct
7 Correct 114 ms 48988 KB Output is correct
8 Correct 117 ms 48832 KB Output is correct
9 Correct 114 ms 48836 KB Output is correct
10 Correct 146 ms 42864 KB Output is correct
11 Correct 132 ms 43068 KB Output is correct
12 Correct 135 ms 42992 KB Output is correct
13 Correct 132 ms 42864 KB Output is correct
14 Correct 132 ms 42864 KB Output is correct
15 Correct 141 ms 36708 KB Output is correct
16 Correct 145 ms 36636 KB Output is correct
17 Correct 163 ms 36888 KB Output is correct
18 Correct 145 ms 36708 KB Output is correct
19 Correct 143 ms 36864 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 7552 KB Output isn't correct
4 Halted 0 ms 0 KB -