| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 57037 | 2018-07-13T16:38:15 Z | dennisstar | None (KOI17_cat) | C++11 | 772 ms | 263168 KB |
#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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 20 ms | 14456 KB | Output is correct |
| 2 | Correct | 15 ms | 14456 KB | Output is correct |
| 3 | Correct | 17 ms | 14480 KB | Output is correct |
| 4 | Correct | 18 ms | 14532 KB | Output is correct |
| 5 | Correct | 17 ms | 15176 KB | Output is correct |
| 6 | Correct | 25 ms | 15176 KB | Output is correct |
| 7 | Correct | 19 ms | 15712 KB | Output is correct |
| 8 | Correct | 23 ms | 15712 KB | Output is correct |
| 9 | Correct | 20 ms | 15932 KB | Output is correct |
| 10 | Correct | 25 ms | 15932 KB | Output is correct |
| 11 | Correct | 22 ms | 15936 KB | Output is correct |
| 12 | Correct | 23 ms | 15936 KB | Output is correct |
| 13 | Correct | 20 ms | 15936 KB | Output is correct |
| 14 | Correct | 21 ms | 15936 KB | Output is correct |
| 15 | Correct | 17 ms | 15936 KB | Output is correct |
| 16 | Correct | 18 ms | 15936 KB | Output is correct |
| 17 | Correct | 15 ms | 15936 KB | Output is correct |
| 18 | Correct | 15 ms | 15936 KB | Output is correct |
| 19 | Correct | 16 ms | 15936 KB | Output is correct |
| 20 | Correct | 19 ms | 16100 KB | Output is correct |
| 21 | Correct | 19 ms | 16176 KB | Output is correct |
| 22 | Correct | 20 ms | 16240 KB | Output is correct |
| 23 | Correct | 16 ms | 16240 KB | Output is correct |
| 24 | Correct | 22 ms | 16240 KB | Output is correct |
| 25 | Correct | 18 ms | 16240 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 506 ms | 38780 KB | Output is correct |
| 2 | Correct | 434 ms | 42680 KB | Output is correct |
| 3 | Correct | 433 ms | 46656 KB | Output is correct |
| 4 | Correct | 455 ms | 50452 KB | Output is correct |
| 5 | Correct | 477 ms | 54420 KB | Output is correct |
| 6 | Correct | 408 ms | 58264 KB | Output is correct |
| 7 | Correct | 567 ms | 62236 KB | Output is correct |
| 8 | Correct | 562 ms | 66328 KB | Output is correct |
| 9 | Correct | 419 ms | 70064 KB | Output is correct |
| 10 | Correct | 542 ms | 73992 KB | Output is correct |
| 11 | Correct | 433 ms | 78536 KB | Output is correct |
| 12 | Correct | 536 ms | 82512 KB | Output is correct |
| 13 | Correct | 561 ms | 86080 KB | Output is correct |
| 14 | Correct | 488 ms | 90144 KB | Output is correct |
| 15 | Correct | 554 ms | 94044 KB | Output is correct |
| 16 | Correct | 446 ms | 103732 KB | Output is correct |
| 17 | Correct | 425 ms | 108948 KB | Output is correct |
| 18 | Correct | 610 ms | 110460 KB | Output is correct |
| 19 | Correct | 503 ms | 115588 KB | Output is correct |
| 20 | Correct | 495 ms | 118212 KB | Output is correct |
| 21 | Correct | 454 ms | 119800 KB | Output is correct |
| 22 | Correct | 559 ms | 135236 KB | Output is correct |
| 23 | Correct | 533 ms | 144084 KB | Output is correct |
| 24 | Correct | 525 ms | 144084 KB | Output is correct |
| 25 | Correct | 508 ms | 149492 KB | Output is correct |
| 26 | Correct | 224 ms | 168508 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 217 ms | 172260 KB | Output is correct |
| 2 | Correct | 267 ms | 176076 KB | Output is correct |
| 3 | Correct | 200 ms | 180144 KB | Output is correct |
| 4 | Correct | 293 ms | 183952 KB | Output is correct |
| 5 | Correct | 216 ms | 187584 KB | Output is correct |
| 6 | Correct | 224 ms | 191268 KB | Output is correct |
| 7 | Correct | 227 ms | 194968 KB | Output is correct |
| 8 | Correct | 227 ms | 198480 KB | Output is correct |
| 9 | Correct | 223 ms | 202052 KB | Output is correct |
| 10 | Correct | 255 ms | 202052 KB | Output is correct |
| 11 | Correct | 264 ms | 202052 KB | Output is correct |
| 12 | Correct | 268 ms | 204792 KB | Output is correct |
| 13 | Correct | 313 ms | 208464 KB | Output is correct |
| 14 | Correct | 292 ms | 211820 KB | Output is correct |
| 15 | Correct | 279 ms | 211820 KB | Output is correct |
| 16 | Correct | 302 ms | 211820 KB | Output is correct |
| 17 | Correct | 273 ms | 214380 KB | Output is correct |
| 18 | Correct | 265 ms | 217940 KB | Output is correct |
| 19 | Correct | 233 ms | 221472 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 20 ms | 14456 KB | Output is correct |
| 2 | Correct | 15 ms | 14456 KB | Output is correct |
| 3 | Correct | 17 ms | 14480 KB | Output is correct |
| 4 | Correct | 18 ms | 14532 KB | Output is correct |
| 5 | Correct | 17 ms | 15176 KB | Output is correct |
| 6 | Correct | 25 ms | 15176 KB | Output is correct |
| 7 | Correct | 19 ms | 15712 KB | Output is correct |
| 8 | Correct | 23 ms | 15712 KB | Output is correct |
| 9 | Correct | 20 ms | 15932 KB | Output is correct |
| 10 | Correct | 25 ms | 15932 KB | Output is correct |
| 11 | Correct | 22 ms | 15936 KB | Output is correct |
| 12 | Correct | 23 ms | 15936 KB | Output is correct |
| 13 | Correct | 20 ms | 15936 KB | Output is correct |
| 14 | Correct | 21 ms | 15936 KB | Output is correct |
| 15 | Correct | 17 ms | 15936 KB | Output is correct |
| 16 | Correct | 18 ms | 15936 KB | Output is correct |
| 17 | Correct | 15 ms | 15936 KB | Output is correct |
| 18 | Correct | 15 ms | 15936 KB | Output is correct |
| 19 | Correct | 16 ms | 15936 KB | Output is correct |
| 20 | Correct | 19 ms | 16100 KB | Output is correct |
| 21 | Correct | 19 ms | 16176 KB | Output is correct |
| 22 | Correct | 20 ms | 16240 KB | Output is correct |
| 23 | Correct | 16 ms | 16240 KB | Output is correct |
| 24 | Correct | 22 ms | 16240 KB | Output is correct |
| 25 | Correct | 18 ms | 16240 KB | Output is correct |
| 26 | Correct | 506 ms | 38780 KB | Output is correct |
| 27 | Correct | 434 ms | 42680 KB | Output is correct |
| 28 | Correct | 433 ms | 46656 KB | Output is correct |
| 29 | Correct | 455 ms | 50452 KB | Output is correct |
| 30 | Correct | 477 ms | 54420 KB | Output is correct |
| 31 | Correct | 408 ms | 58264 KB | Output is correct |
| 32 | Correct | 567 ms | 62236 KB | Output is correct |
| 33 | Correct | 562 ms | 66328 KB | Output is correct |
| 34 | Correct | 419 ms | 70064 KB | Output is correct |
| 35 | Correct | 542 ms | 73992 KB | Output is correct |
| 36 | Correct | 433 ms | 78536 KB | Output is correct |
| 37 | Correct | 536 ms | 82512 KB | Output is correct |
| 38 | Correct | 561 ms | 86080 KB | Output is correct |
| 39 | Correct | 488 ms | 90144 KB | Output is correct |
| 40 | Correct | 554 ms | 94044 KB | Output is correct |
| 41 | Correct | 446 ms | 103732 KB | Output is correct |
| 42 | Correct | 425 ms | 108948 KB | Output is correct |
| 43 | Correct | 610 ms | 110460 KB | Output is correct |
| 44 | Correct | 503 ms | 115588 KB | Output is correct |
| 45 | Correct | 495 ms | 118212 KB | Output is correct |
| 46 | Correct | 454 ms | 119800 KB | Output is correct |
| 47 | Correct | 559 ms | 135236 KB | Output is correct |
| 48 | Correct | 533 ms | 144084 KB | Output is correct |
| 49 | Correct | 525 ms | 144084 KB | Output is correct |
| 50 | Correct | 508 ms | 149492 KB | Output is correct |
| 51 | Correct | 224 ms | 168508 KB | Output is correct |
| 52 | Correct | 217 ms | 172260 KB | Output is correct |
| 53 | Correct | 267 ms | 176076 KB | Output is correct |
| 54 | Correct | 200 ms | 180144 KB | Output is correct |
| 55 | Correct | 293 ms | 183952 KB | Output is correct |
| 56 | Correct | 216 ms | 187584 KB | Output is correct |
| 57 | Correct | 224 ms | 191268 KB | Output is correct |
| 58 | Correct | 227 ms | 194968 KB | Output is correct |
| 59 | Correct | 227 ms | 198480 KB | Output is correct |
| 60 | Correct | 223 ms | 202052 KB | Output is correct |
| 61 | Correct | 255 ms | 202052 KB | Output is correct |
| 62 | Correct | 264 ms | 202052 KB | Output is correct |
| 63 | Correct | 268 ms | 204792 KB | Output is correct |
| 64 | Correct | 313 ms | 208464 KB | Output is correct |
| 65 | Correct | 292 ms | 211820 KB | Output is correct |
| 66 | Correct | 279 ms | 211820 KB | Output is correct |
| 67 | Correct | 302 ms | 211820 KB | Output is correct |
| 68 | Correct | 273 ms | 214380 KB | Output is correct |
| 69 | Correct | 265 ms | 217940 KB | Output is correct |
| 70 | Correct | 233 ms | 221472 KB | Output is correct |
| 71 | Correct | 760 ms | 239152 KB | Output is correct |
| 72 | Correct | 721 ms | 240632 KB | Output is correct |
| 73 | Correct | 675 ms | 243056 KB | Output is correct |
| 74 | Correct | 629 ms | 248316 KB | Output is correct |
| 75 | Correct | 656 ms | 248380 KB | Output is correct |
| 76 | Correct | 772 ms | 251408 KB | Output is correct |
| 77 | Correct | 700 ms | 251408 KB | Output is correct |
| 78 | Correct | 637 ms | 252684 KB | Output is correct |
| 79 | Runtime error | 697 ms | 263168 KB | Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 80 | Halted | 0 ms | 0 KB | - |