답안 #57040 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57040	2018-07-13T16:42:07 Z	dennisstar	산만한 고양이 (KOI17_cat)	C++11	100 / 100	680 ms	111636 KB

#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

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.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14584 KB	Output is correct
2	Correct	18 ms	14584 KB	Output is correct
3	Correct	17 ms	14600 KB	Output is correct
4	Correct	17 ms	14600 KB	Output is correct
5	Correct	20 ms	15076 KB	Output is correct
6	Correct	17 ms	15076 KB	Output is correct
7	Correct	22 ms	15472 KB	Output is correct
8	Correct	27 ms	15472 KB	Output is correct
9	Correct	22 ms	15696 KB	Output is correct
10	Correct	19 ms	15696 KB	Output is correct
11	Correct	22 ms	15708 KB	Output is correct
12	Correct	19 ms	15884 KB	Output is correct
13	Correct	20 ms	15884 KB	Output is correct
14	Correct	23 ms	15884 KB	Output is correct
15	Correct	20 ms	15884 KB	Output is correct
16	Correct	17 ms	15884 KB	Output is correct
17	Correct	16 ms	15884 KB	Output is correct
18	Correct	17 ms	15884 KB	Output is correct
19	Correct	15 ms	15884 KB	Output is correct
20	Correct	17 ms	15964 KB	Output is correct
21	Correct	18 ms	16016 KB	Output is correct
22	Correct	23 ms	16064 KB	Output is correct
23	Correct	16 ms	16064 KB	Output is correct
24	Correct	20 ms	16064 KB	Output is correct
25	Correct	16 ms	16064 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	521 ms	38652 KB	Output is correct
2	Correct	536 ms	42644 KB	Output is correct
3	Correct	414 ms	46532 KB	Output is correct
4	Correct	584 ms	50292 KB	Output is correct
5	Correct	457 ms	54180 KB	Output is correct
6	Correct	559 ms	58144 KB	Output is correct
7	Correct	573 ms	58772 KB	Output is correct
8	Correct	551 ms	58772 KB	Output is correct
9	Correct	551 ms	58772 KB	Output is correct
10	Correct	443 ms	58772 KB	Output is correct
11	Correct	547 ms	59448 KB	Output is correct
12	Correct	534 ms	59448 KB	Output is correct
13	Correct	550 ms	59448 KB	Output is correct
14	Correct	475 ms	59448 KB	Output is correct
15	Correct	440 ms	59448 KB	Output is correct
16	Correct	479 ms	65224 KB	Output is correct
17	Correct	543 ms	66612 KB	Output is correct
18	Correct	520 ms	66612 KB	Output is correct
19	Correct	626 ms	66612 KB	Output is correct
20	Correct	448 ms	66612 KB	Output is correct
21	Correct	464 ms	66612 KB	Output is correct
22	Correct	449 ms	73264 KB	Output is correct
23	Correct	515 ms	78180 KB	Output is correct
24	Correct	501 ms	78180 KB	Output is correct
25	Correct	461 ms	78180 KB	Output is correct
26	Correct	195 ms	90972 KB	Output is correct

Subtask #3
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	90980 KB	Output is correct
2	Correct	316 ms	90980 KB	Output is correct
3	Correct	260 ms	91132 KB	Output is correct
4	Correct	227 ms	91132 KB	Output is correct
5	Correct	223 ms	91132 KB	Output is correct
6	Correct	228 ms	91172 KB	Output is correct
7	Correct	201 ms	91172 KB	Output is correct
8	Correct	204 ms	91172 KB	Output is correct
9	Correct	236 ms	91172 KB	Output is correct
10	Correct	258 ms	91172 KB	Output is correct
11	Correct	219 ms	91172 KB	Output is correct
12	Correct	212 ms	91172 KB	Output is correct
13	Correct	214 ms	91172 KB	Output is correct
14	Correct	212 ms	91172 KB	Output is correct
15	Correct	237 ms	91172 KB	Output is correct
16	Correct	335 ms	91172 KB	Output is correct
17	Correct	233 ms	91172 KB	Output is correct
18	Correct	256 ms	91172 KB	Output is correct
19	Correct	257 ms	91172 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14584 KB	Output is correct
2	Correct	18 ms	14584 KB	Output is correct
3	Correct	17 ms	14600 KB	Output is correct
4	Correct	17 ms	14600 KB	Output is correct
5	Correct	20 ms	15076 KB	Output is correct
6	Correct	17 ms	15076 KB	Output is correct
7	Correct	22 ms	15472 KB	Output is correct
8	Correct	27 ms	15472 KB	Output is correct
9	Correct	22 ms	15696 KB	Output is correct
10	Correct	19 ms	15696 KB	Output is correct
11	Correct	22 ms	15708 KB	Output is correct
12	Correct	19 ms	15884 KB	Output is correct
13	Correct	20 ms	15884 KB	Output is correct
14	Correct	23 ms	15884 KB	Output is correct
15	Correct	20 ms	15884 KB	Output is correct
16	Correct	17 ms	15884 KB	Output is correct
17	Correct	16 ms	15884 KB	Output is correct
18	Correct	17 ms	15884 KB	Output is correct
19	Correct	15 ms	15884 KB	Output is correct
20	Correct	17 ms	15964 KB	Output is correct
21	Correct	18 ms	16016 KB	Output is correct
22	Correct	23 ms	16064 KB	Output is correct
23	Correct	16 ms	16064 KB	Output is correct
24	Correct	20 ms	16064 KB	Output is correct
25	Correct	16 ms	16064 KB	Output is correct
26	Correct	521 ms	38652 KB	Output is correct
27	Correct	536 ms	42644 KB	Output is correct
28	Correct	414 ms	46532 KB	Output is correct
29	Correct	584 ms	50292 KB	Output is correct
30	Correct	457 ms	54180 KB	Output is correct
31	Correct	559 ms	58144 KB	Output is correct
32	Correct	573 ms	58772 KB	Output is correct
33	Correct	551 ms	58772 KB	Output is correct
34	Correct	551 ms	58772 KB	Output is correct
35	Correct	443 ms	58772 KB	Output is correct
36	Correct	547 ms	59448 KB	Output is correct
37	Correct	534 ms	59448 KB	Output is correct
38	Correct	550 ms	59448 KB	Output is correct
39	Correct	475 ms	59448 KB	Output is correct
40	Correct	440 ms	59448 KB	Output is correct
41	Correct	479 ms	65224 KB	Output is correct
42	Correct	543 ms	66612 KB	Output is correct
43	Correct	520 ms	66612 KB	Output is correct
44	Correct	626 ms	66612 KB	Output is correct
45	Correct	448 ms	66612 KB	Output is correct
46	Correct	464 ms	66612 KB	Output is correct
47	Correct	449 ms	73264 KB	Output is correct
48	Correct	515 ms	78180 KB	Output is correct
49	Correct	501 ms	78180 KB	Output is correct
50	Correct	461 ms	78180 KB	Output is correct
51	Correct	195 ms	90972 KB	Output is correct
52	Correct	201 ms	90980 KB	Output is correct
53	Correct	316 ms	90980 KB	Output is correct
54	Correct	260 ms	91132 KB	Output is correct
55	Correct	227 ms	91132 KB	Output is correct
56	Correct	223 ms	91132 KB	Output is correct
57	Correct	228 ms	91172 KB	Output is correct
58	Correct	201 ms	91172 KB	Output is correct
59	Correct	204 ms	91172 KB	Output is correct
60	Correct	236 ms	91172 KB	Output is correct
61	Correct	258 ms	91172 KB	Output is correct
62	Correct	219 ms	91172 KB	Output is correct
63	Correct	212 ms	91172 KB	Output is correct
64	Correct	214 ms	91172 KB	Output is correct
65	Correct	212 ms	91172 KB	Output is correct
66	Correct	237 ms	91172 KB	Output is correct
67	Correct	335 ms	91172 KB	Output is correct
68	Correct	233 ms	91172 KB	Output is correct
69	Correct	256 ms	91172 KB	Output is correct
70	Correct	257 ms	91172 KB	Output is correct
71	Correct	495 ms	91172 KB	Output is correct
72	Correct	517 ms	91172 KB	Output is correct
73	Correct	571 ms	91172 KB	Output is correct
74	Correct	621 ms	91172 KB	Output is correct
75	Correct	649 ms	91172 KB	Output is correct
76	Correct	526 ms	91172 KB	Output is correct
77	Correct	504 ms	91172 KB	Output is correct
78	Correct	544 ms	91172 KB	Output is correct
79	Correct	540 ms	91172 KB	Output is correct
80	Correct	535 ms	91172 KB	Output is correct
81	Correct	667 ms	91172 KB	Output is correct
82	Correct	539 ms	100368 KB	Output is correct
83	Correct	557 ms	104660 KB	Output is correct
84	Correct	680 ms	106620 KB	Output is correct
85	Correct	561 ms	111636 KB	Output is correct
86	Correct	494 ms	111636 KB	Output is correct
87	Correct	416 ms	111636 KB	Output is correct
88	Correct	230 ms	111636 KB	Output is correct
89	Correct	244 ms	111636 KB	Output is correct
90	Correct	258 ms	111636 KB	Output is correct

답안 #57040

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 23.0 / 23.0

Subtask #4 55.0 / 55.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
23.0 / 23.0

Subtask #4
55.0 / 55.0