| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 15990 | 2015-08-05T02:34:36 Z | myungwoo | Senior Postmen (BOI14_postmen) | C++14 | 356 ms | 25044 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define pb push_back
#define sz(v) ((int)(v).size())
int N, M, K;
int last[MAXN], to[MAXN*2], en[MAXN*2], prv[MAXN*2];
bool VE[MAXN];
vector <int> path;
void add_edge(int a, int b, int e)
{
to[++K] = b; en[K] = e; prv[K] = last[a]; last[a] = K;
to[++K] = a; en[K] = e; prv[K] = last[b]; last[b] = K;
}
void dfs(int n)
{
stack <int> stk;
stk.push(n);
while (!stk.empty()){
int n = stk.top();
bool sw = 0;
for (int i=last[n];i;i=prv[i]){
int t = to[i], e = en[i];
last[n] = prv[i];
if (VE[e]) continue;
VE[e] = 1;
stk.push(t); sw = 1;
break;
}
if (!sw) path.pb(n), stk.pop();
}
}
int main()
{
scanf("%d%d", &N, &M);
for (int i=1;i<=M;i++){
int a, b;
scanf("%d%d", &a, &b);
add_edge(a, b, i);
}
dfs(1);
stack <int> stk;
vector <int> vis(N+1, 0);
for (int t: path){
if (vis[t]){
while (!stk.empty() && stk.top() != t) printf("%d ", stk.top()), vis[stk.top()] = 0, stk.pop();
printf("%d\n", t);
}else{
stk.push(t);
vis[t] = 1;
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 4 ms | 360 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 6 ms | 512 KB | Output is correct |
| 5 | Correct | 6 ms | 384 KB | Output is correct |
| 6 | Correct | 8 ms | 512 KB | Output is correct |
| 7 | Correct | 11 ms | 1024 KB | Output is correct |
| 8 | Correct | 7 ms | 384 KB | Output is correct |
| 9 | Correct | 40 ms | 3956 KB | Output is correct |
| 10 | Correct | 6 ms | 512 KB | Output is correct |
| 11 | Correct | 5 ms | 512 KB | Output is correct |
| 12 | Correct | 43 ms | 4028 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 5 ms | 384 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 7 ms | 512 KB | Output is correct |
| 5 | Correct | 6 ms | 384 KB | Output is correct |
| 6 | Correct | 6 ms | 640 KB | Output is correct |
| 7 | Correct | 10 ms | 896 KB | Output is correct |
| 8 | Correct | 6 ms | 452 KB | Output is correct |
| 9 | Correct | 40 ms | 3932 KB | Output is correct |
| 10 | Correct | 7 ms | 432 KB | Output is correct |
| 11 | Correct | 7 ms | 512 KB | Output is correct |
| 12 | Correct | 45 ms | 4036 KB | Output is correct |
| 13 | Correct | 50 ms | 5032 KB | Output is correct |
| 14 | Correct | 52 ms | 4560 KB | Output is correct |
| 15 | Correct | 45 ms | 4260 KB | Output is correct |
| 16 | Correct | 58 ms | 5028 KB | Output is correct |
| 17 | Correct | 60 ms | 4432 KB | Output is correct |
| 18 | Correct | 54 ms | 4536 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 384 KB | Output is correct |
| 2 | Correct | 5 ms | 384 KB | Output is correct |
| 3 | Correct | 5 ms | 384 KB | Output is correct |
| 4 | Correct | 7 ms | 512 KB | Output is correct |
| 5 | Correct | 5 ms | 384 KB | Output is correct |
| 6 | Correct | 6 ms | 512 KB | Output is correct |
| 7 | Correct | 10 ms | 1024 KB | Output is correct |
| 8 | Correct | 6 ms | 384 KB | Output is correct |
| 9 | Correct | 52 ms | 3932 KB | Output is correct |
| 10 | Correct | 6 ms | 512 KB | Output is correct |
| 11 | Correct | 7 ms | 512 KB | Output is correct |
| 12 | Correct | 59 ms | 4012 KB | Output is correct |
| 13 | Correct | 51 ms | 5028 KB | Output is correct |
| 14 | Correct | 54 ms | 4544 KB | Output is correct |
| 15 | Correct | 46 ms | 4260 KB | Output is correct |
| 16 | Correct | 47 ms | 5028 KB | Output is correct |
| 17 | Correct | 58 ms | 4456 KB | Output is correct |
| 18 | Correct | 47 ms | 4644 KB | Output is correct |
| 19 | Correct | 299 ms | 23940 KB | Output is correct |
| 20 | Correct | 327 ms | 21908 KB | Output is correct |
| 21 | Correct | 310 ms | 21016 KB | Output is correct |
| 22 | Correct | 342 ms | 25044 KB | Output is correct |
| 23 | Correct | 198 ms | 17984 KB | Output is correct |
| 24 | Correct | 356 ms | 21724 KB | Output is correct |
| 25 | Correct | 310 ms | 22360 KB | Output is correct |