# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197490 | 2020-01-21T13:08:24 Z | dndhk | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 67444 KB |
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 500000; int N, M; vector<int> gp[MAX_N+1]; bool chk[MAX_N+1]; pii p[MAX_N+1]; vector<int> v; vector<int> nxt[MAX_N+1]; bool vst[MAX_N+1]; vector<int> vt; int main(){ scanf("%d%d", &N, &M); for(int i=1; i<=M; i++){ int a, b; scanf("%d%d", &a, &b); gp[a].pb(i); gp[b].pb(i); p[i] = {a, b}; } for(int i=1; i<=N; i++){ for(int j=0; j<gp[i].size(); j+=2){ nxt[gp[i][j]].pb(gp[i][j+1]); nxt[gp[i][j+1]].pb(gp[i][j]); } } for(int i=1; i<=M; i++){ if(!chk[i]){ chk[i] = true; chk[nxt[i][0]] = true; v.pb(nxt[i][0]); v.pb(i); int n = nxt[i][1]; while(1){ chk[n] = true; v.pb(n); if(chk[nxt[n][0]] && chk[nxt[n][1]]){ break; } if(chk[nxt[n][0]]){ n = nxt[n][1]; }else{ n = nxt[n][0]; } } int x; if(p[v.back()].first==p[v[0]].first || p[v.back()].first==p[v[0]].second){ x = p[v.back()].first; }else{ x = p[v.back()].second; } while(!v.empty()){ x = p[v.back()].first+p[v.back()].second-x; if(vst[x]){ while(vt.back()!=x){ vst[vt.back()] = false; printf("%d ", vt.back()); vt.pop_back(); } printf("%d\n", x); }else{ vst[x] = true; vt.pb(x); } v.pop_back(); } if(!vt.empty()){ while(!vt.empty()){ vst[vt.back()] = false; printf("%d ", vt.back()); vt.pop_back(); }printf("\n"); } } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 23784 KB | Output is correct |
2 | Correct | 25 ms | 23808 KB | Output is correct |
3 | Correct | 19 ms | 23808 KB | Output is correct |
4 | Correct | 20 ms | 24064 KB | Output is correct |
5 | Correct | 23 ms | 23932 KB | Output is correct |
6 | Correct | 19 ms | 24064 KB | Output is correct |
7 | Correct | 33 ms | 24704 KB | Output is correct |
8 | Correct | 20 ms | 24064 KB | Output is correct |
9 | Correct | 98 ms | 29432 KB | Output is correct |
10 | Correct | 22 ms | 24064 KB | Output is correct |
11 | Correct | 20 ms | 24040 KB | Output is correct |
12 | Correct | 101 ms | 29560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23808 KB | Output is correct |
2 | Correct | 20 ms | 23784 KB | Output is correct |
3 | Correct | 18 ms | 23872 KB | Output is correct |
4 | Correct | 27 ms | 24096 KB | Output is correct |
5 | Correct | 23 ms | 23936 KB | Output is correct |
6 | Correct | 25 ms | 24064 KB | Output is correct |
7 | Correct | 28 ms | 24704 KB | Output is correct |
8 | Correct | 22 ms | 23936 KB | Output is correct |
9 | Correct | 112 ms | 29496 KB | Output is correct |
10 | Correct | 21 ms | 24064 KB | Output is correct |
11 | Correct | 21 ms | 24064 KB | Output is correct |
12 | Correct | 114 ms | 29688 KB | Output is correct |
13 | Correct | 125 ms | 32572 KB | Output is correct |
14 | Correct | 149 ms | 30848 KB | Output is correct |
15 | Correct | 164 ms | 31220 KB | Output is correct |
16 | Correct | 132 ms | 32600 KB | Output is correct |
17 | Correct | 159 ms | 30840 KB | Output is correct |
18 | Correct | 141 ms | 31332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23808 KB | Output is correct |
2 | Correct | 20 ms | 23808 KB | Output is correct |
3 | Correct | 21 ms | 23808 KB | Output is correct |
4 | Correct | 27 ms | 24040 KB | Output is correct |
5 | Correct | 18 ms | 23936 KB | Output is correct |
6 | Correct | 22 ms | 24112 KB | Output is correct |
7 | Correct | 28 ms | 24720 KB | Output is correct |
8 | Correct | 23 ms | 23936 KB | Output is correct |
9 | Correct | 111 ms | 29404 KB | Output is correct |
10 | Correct | 21 ms | 24064 KB | Output is correct |
11 | Correct | 23 ms | 24064 KB | Output is correct |
12 | Correct | 115 ms | 29688 KB | Output is correct |
13 | Correct | 138 ms | 32600 KB | Output is correct |
14 | Correct | 134 ms | 30808 KB | Output is correct |
15 | Correct | 128 ms | 31180 KB | Output is correct |
16 | Correct | 158 ms | 32604 KB | Output is correct |
17 | Correct | 145 ms | 30752 KB | Output is correct |
18 | Correct | 137 ms | 31428 KB | Output is correct |
19 | Execution timed out | 788 ms | 67444 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |