# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62882 | 2018-07-30T16:23:00 Z | IvanC | Senior Postmen (BOI14_postmen) | C++17 | 500 ms | 76756 KB |
#include <bits/stdc++.h> #define gc getchar_unlocked inline void getint(int &x){ register int c = gc(); x = 0; for(;(c<48 || c>57);c = gc()); for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} } inline void print(int n){ char buf[11]; buf[10] = ' '; int i = 9; while (n) { buf[i--] = n % 10 + '0'; n /= 10; } while (buf[i] != ' ') putchar_unlocked(buf[++i]); } 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++){ getint(e1[i]); getint(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]) print(j); printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Correct | 13 ms | 12032 KB | Output is correct |
3 | Correct | 11 ms | 12160 KB | Output is correct |
4 | Correct | 13 ms | 12288 KB | Output is correct |
5 | Correct | 13 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 19 ms | 12672 KB | Output is correct |
8 | Correct | 15 ms | 12392 KB | Output is correct |
9 | Correct | 34 ms | 15224 KB | Output is correct |
10 | Correct | 13 ms | 12288 KB | Output is correct |
11 | Correct | 13 ms | 12288 KB | Output is correct |
12 | Correct | 31 ms | 15428 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12136 KB | Output is correct |
2 | Correct | 14 ms | 12032 KB | Output is correct |
3 | Correct | 14 ms | 12032 KB | Output is correct |
4 | Correct | 16 ms | 12288 KB | Output is correct |
5 | Correct | 13 ms | 12160 KB | Output is correct |
6 | Correct | 15 ms | 12288 KB | Output is correct |
7 | Correct | 16 ms | 12672 KB | Output is correct |
8 | Correct | 15 ms | 12288 KB | Output is correct |
9 | Correct | 27 ms | 15232 KB | Output is correct |
10 | Correct | 13 ms | 12288 KB | Output is correct |
11 | Correct | 12 ms | 12264 KB | Output is correct |
12 | Correct | 29 ms | 15480 KB | Output is correct |
13 | Correct | 60 ms | 24948 KB | Output is correct |
14 | Correct | 54 ms | 18224 KB | Output is correct |
15 | Correct | 65 ms | 18668 KB | Output is correct |
16 | Correct | 89 ms | 24936 KB | Output is correct |
17 | Correct | 99 ms | 18712 KB | Output is correct |
18 | Correct | 68 ms | 19888 KB | Output is correct |
# | 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 | 26 ms | 12032 KB | Output is correct |
4 | Correct | 16 ms | 12288 KB | Output is correct |
5 | Correct | 14 ms | 12212 KB | Output is correct |
6 | Correct | 15 ms | 12288 KB | Output is correct |
7 | Correct | 16 ms | 12672 KB | Output is correct |
8 | Correct | 14 ms | 12448 KB | Output is correct |
9 | Correct | 35 ms | 15208 KB | Output is correct |
10 | Correct | 13 ms | 12288 KB | Output is correct |
11 | Correct | 17 ms | 12288 KB | Output is correct |
12 | Correct | 35 ms | 15488 KB | Output is correct |
13 | Correct | 97 ms | 25320 KB | Output is correct |
14 | Correct | 63 ms | 18500 KB | Output is correct |
15 | Correct | 61 ms | 18924 KB | Output is correct |
16 | Correct | 75 ms | 25204 KB | Output is correct |
17 | Correct | 81 ms | 18924 KB | Output is correct |
18 | Correct | 104 ms | 20248 KB | Output is correct |
19 | Execution timed out | 534 ms | 76756 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |