# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
197812 | 2020-01-23T11:25:00 Z | dndhk | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 34196 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<pii> gp[MAX_N+1]; bool chk[MAX_N+1]; bool vst[MAX_N+1]; vector<int> v; void solve(int x){ vst[x] = true; v.pb(x); while(!gp[x].empty() && chk[gp[x].back().second]) gp[x].pop_back(); chk[gp[x].back().second] = true; int nxt = gp[x].back().first; gp[x].pop_back(); if(vst[nxt]){ while(v.back()!=nxt){ printf("%d ", v.back()); vst[v.back()] = false; v.pop_back(); } vst[v.back()] = false; printf("%d\n", v.back()); v.pop_back(); if(v.empty()) return; else solve(nxt); } else solve(nxt); } 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({b, i}); gp[b].pb({a, i}); } int idx = 1; while(idx<=N){ while(!gp[idx].empty() && chk[gp[idx].back().second]) gp[idx].pop_back(); if(gp[idx].empty()) idx++; else{ int n = idx; while(1){ vst[n] = true; v.pb(n); while(!gp[n].empty() && chk[gp[n].back().second]) gp[n].pop_back(); chk[gp[n].back().second] = true; int nxt = gp[n].back().first; gp[n].pop_back(); if(vst[nxt]){ while(v.back()!=nxt){ vst[v.back()] = false; printf("%d ", v.back()); v.pop_back(); } vst[v.back()] = false; printf("%d\n", v.back()); v.pop_back(); if(v.empty()) break; else n = nxt; }else{ n = nxt; } } } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 12032 KB | Output is correct |
2 | Correct | 14 ms | 12032 KB | Output is correct |
3 | Correct | 14 ms | 12032 KB | Output is correct |
4 | Correct | 12 ms | 12160 KB | Output is correct |
5 | Correct | 12 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12160 KB | Output is correct |
7 | Correct | 17 ms | 12672 KB | Output is correct |
8 | Correct | 13 ms | 12160 KB | Output is correct |
9 | Correct | 49 ms | 14456 KB | Output is correct |
10 | Correct | 13 ms | 12160 KB | Output is correct |
11 | Correct | 16 ms | 12228 KB | Output is correct |
12 | Correct | 63 ms | 14840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12008 KB | Output is correct |
2 | Correct | 11 ms | 12032 KB | Output is correct |
3 | Correct | 10 ms | 12160 KB | Output is correct |
4 | Correct | 17 ms | 12160 KB | Output is correct |
5 | Correct | 12 ms | 12160 KB | Output is correct |
6 | Correct | 17 ms | 12160 KB | Output is correct |
7 | Correct | 20 ms | 12520 KB | Output is correct |
8 | Correct | 17 ms | 12160 KB | Output is correct |
9 | Correct | 78 ms | 14456 KB | Output is correct |
10 | Correct | 13 ms | 12160 KB | Output is correct |
11 | Correct | 16 ms | 12160 KB | Output is correct |
12 | Correct | 58 ms | 14816 KB | Output is correct |
13 | Correct | 87 ms | 16500 KB | Output is correct |
14 | Correct | 83 ms | 15736 KB | Output is correct |
15 | Correct | 83 ms | 15264 KB | Output is correct |
16 | Correct | 95 ms | 16480 KB | Output is correct |
17 | Correct | 101 ms | 15548 KB | Output is correct |
18 | Correct | 99 ms | 15968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12032 KB | Output is correct |
2 | Correct | 12 ms | 12032 KB | Output is correct |
3 | Correct | 13 ms | 12032 KB | Output is correct |
4 | Correct | 17 ms | 12160 KB | Output is correct |
5 | Correct | 13 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12160 KB | Output is correct |
7 | Correct | 17 ms | 12544 KB | Output is correct |
8 | Correct | 14 ms | 12160 KB | Output is correct |
9 | Correct | 55 ms | 14432 KB | Output is correct |
10 | Correct | 13 ms | 12160 KB | Output is correct |
11 | Correct | 15 ms | 12136 KB | Output is correct |
12 | Correct | 56 ms | 14916 KB | Output is correct |
13 | Correct | 93 ms | 16476 KB | Output is correct |
14 | Correct | 91 ms | 15836 KB | Output is correct |
15 | Correct | 80 ms | 15316 KB | Output is correct |
16 | Correct | 85 ms | 16500 KB | Output is correct |
17 | Correct | 100 ms | 15632 KB | Output is correct |
18 | Correct | 86 ms | 15864 KB | Output is correct |
19 | Execution timed out | 541 ms | 34196 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |