# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42314 | 2018-02-26T00:54:48 Z | IvanC | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 76280 KB |
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = 5*1e5 + 10; int N,M,e1[MAXN],e2[MAXN],e3[MAXN],marcado[MAXN],ptr[MAXN]; vi grafo[MAXN],pilha; vector<vi> resposta; int dfs(int v){ //printf("DFS %d\n",v); marcado[v] = 1; for(;ptr[v] < grafo[v].size();ptr[v]++){ int idx = grafo[v][ptr[v]]; if(e3[idx] == 1) continue; e3[idx] = 1; int u = (e1[idx] != v) ? (e1[idx]) : (e2[idx]); if(marcado[u]){ marcado[v] = 0; pilha.push_back(v); return u; } int ret = dfs(u); if(ret == v){ pilha.push_back(v); resposta.push_back(pilha); pilha.clear(); } else{ marcado[v] = 0; pilha.push_back(v); return ret; } } marcado[v] = 0; pilha.clear(); return -1; } int main(){ scanf("%d %d",&N,&M); for(int i = 1;i<=M;i++){ scanf("%d %d",&e1[i],&e2[i]); grafo[e1[i]].push_back(i); grafo[e2[i]].push_back(i); } for(int i = 1;i<=N;i++){ dfs(i); } for(int i = 0;i<resposta.size();i++){ for(int j : resposta[i]) printf("%d ",j); printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12032 KB | Output is correct |
2 | Correct | 11 ms | 12032 KB | Output is correct |
3 | Correct | 11 ms | 12032 KB | Output is correct |
4 | Correct | 12 ms | 12288 KB | Output is correct |
5 | Correct | 12 ms | 12160 KB | Output is correct |
6 | Correct | 14 ms | 12288 KB | Output is correct |
7 | Correct | 22 ms | 12672 KB | Output is correct |
8 | Correct | 15 ms | 12288 KB | Output is correct |
9 | Correct | 53 ms | 15128 KB | Output is correct |
10 | Correct | 16 ms | 12288 KB | Output is correct |
11 | Correct | 12 ms | 12288 KB | Output is correct |
12 | Correct | 56 ms | 15480 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12160 KB | Output is correct |
2 | Correct | 12 ms | 12160 KB | Output is correct |
3 | Correct | 13 ms | 12032 KB | Output is correct |
4 | Correct | 13 ms | 12288 KB | Output is correct |
5 | Correct | 12 ms | 12172 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 18 ms | 12672 KB | Output is correct |
8 | Correct | 12 ms | 12416 KB | Output is correct |
9 | Correct | 50 ms | 15224 KB | Output is correct |
10 | Correct | 16 ms | 12264 KB | Output is correct |
11 | Correct | 16 ms | 12264 KB | Output is correct |
12 | Correct | 63 ms | 15456 KB | Output is correct |
13 | Correct | 137 ms | 25052 KB | Output is correct |
14 | Correct | 95 ms | 18224 KB | Output is correct |
15 | Correct | 104 ms | 18668 KB | Output is correct |
16 | Correct | 115 ms | 24948 KB | Output is correct |
17 | Correct | 101 ms | 18608 KB | Output is correct |
18 | Correct | 105 ms | 19996 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12032 KB | Output is correct |
2 | Correct | 11 ms | 12160 KB | Output is correct |
3 | Correct | 13 ms | 12032 KB | Output is correct |
4 | Correct | 13 ms | 12288 KB | Output is correct |
5 | Correct | 14 ms | 12136 KB | Output is correct |
6 | Correct | 14 ms | 12288 KB | Output is correct |
7 | Correct | 24 ms | 12672 KB | Output is correct |
8 | Correct | 13 ms | 12416 KB | Output is correct |
9 | Correct | 52 ms | 15144 KB | Output is correct |
10 | Correct | 14 ms | 12288 KB | Output is correct |
11 | Correct | 15 ms | 12288 KB | Output is correct |
12 | Correct | 56 ms | 15480 KB | Output is correct |
13 | Correct | 106 ms | 24948 KB | Output is correct |
14 | Correct | 90 ms | 18200 KB | Output is correct |
15 | Correct | 108 ms | 18772 KB | Output is correct |
16 | Correct | 105 ms | 24948 KB | Output is correct |
17 | Correct | 117 ms | 18684 KB | Output is correct |
18 | Correct | 105 ms | 19992 KB | Output is correct |
19 | Execution timed out | 667 ms | 76280 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |