Submission #332160

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332160	2020-12-01T15:04:02 Z	oolimry	None (KOI17_cat)	C++14	23 / 100	263 ms	49004 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);
		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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	263 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	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

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