Submission #57037

#	Time	Username	Problem	Language	Result	Execution time	Memory
57037		dennisstar	산만한 고양이 (KOI17_cat)	C++11	45 / 100	772 ms	263168 KiB

cat

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> V[300010], C[300010];
int cnt[300010], P[300010], W[300010], S[300010];
//P: parent node W: weak node S: strong node
void dfs(int lev, int par)
{
	int sv, i;
	for (i=0; i<(int)V[lev].size(); i++) {
		if (V[lev][i]==par) continue;
		if(!cnt[V[lev][i]]) {
			cnt[V[lev][i]]=cnt[lev]+1;
			C[lev].push_back(V[lev][i]);
			sv=S[lev];
			dfs(V[lev][i], lev);
			P[V[lev][i]]=S[lev]-sv;
			S[lev]+=S[V[lev][i]], W[lev]+=W[V[lev][i]];
		}
		else if (cnt[lev]>cnt[V[lev][i]]) W[lev]++,S[V[lev][i]]++;
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	int i, j, k;
	long long sum=0;
	for (i=0; i<M; i++) {
		scanf("%d %d", &j, &k);
		V[j].push_back(k);
		V[k].push_back(j);
	}
	cnt[1]=1; dfs(1, 0);
	for (i=1; i<=N; i++) {
		if (M-N+1!=W[i]) continue;
		for (j=0; j<(int)C[i].size(); j++) {
			if (S[C[i][j]]||W[C[i][j]]-P[C[i][j]]>1) break;
		}
		if (j!=(int)C[i].size()) continue;
		sum+=i;
	}
	printf("%lld", sum);
	return 0;
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
cat.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &j, &k);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 55