Submission #332154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332154	2020-12-01T15:00:14 Z	oolimry	None (KOI17_cat)	C++14	23 / 100	260 ms	49072 KB

cat

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	260 ms	25708 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-