Submission #57040

#	Time	Username	Problem	Language	Result	Execution time	Memory
57040		dennisstar	산만한 고양이 (KOI17_cat)	C++11	100 / 100	680 ms	111636 KiB

cat

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> V[300001], C[300001];
int cnt[300001], P[300001], W[300001], S[300001];
//P: parent node W: weak node S: strong node
void dfs(int lev, int par)
{
	int ch, sv, i; //ch 안쓰면 터져버린다;;
	for (i=0; i<(int)V[lev].size(); i++) {
		ch=V[lev][i];
		if (ch==par) continue;
		if(!cnt[ch]) {
			cnt[ch]=cnt[lev]+1;
			C[lev].push_back(ch);
			sv=S[lev];
			dfs(ch, lev);
			P[ch]=S[lev]-sv;
			S[lev]+=S[ch], W[lev]+=W[ch];
		}
		else if (cnt[lev]>cnt[ch]) W[lev]++,S[ch]++;
	}
}
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:26: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:30: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: 55 / 55