Submission #332168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332168	2020-12-01T15:13:40 Z	oolimry	None (KOI17_cat)	C++14	23 / 100	266 ms	45036 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(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

#	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	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	266 ms	21792 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	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

#	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	7404 KB	Output isn't correct
4	Halted	0 ms	0 KB	-