Submission #332154

#	Time	Username	Problem	Language	Result	Execution time	Memory
332154		oolimry	산만한 고양이 (KOI17_cat)	C++14	23 / 100	260 ms	49072 KiB

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
• Subtask 2: 0 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 55