# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88747 | 2018-12-08T11:48:42 Z | popovicirobert | Senior Postmen (BOI14_postmen) | C++14 | 14 ms | 12136 KB |
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; const int MAXBUF = (1 << 17); char buf[MAXBUF]; int pbuf = MAXBUF; inline char nextch() { if(pbuf == MAXBUF) { fread(buf, 1, MAXBUF, stdin); pbuf = 0; } return buf[pbuf++]; } inline int getnr() { char ch = nextch(); while(!isdigit(ch)) { ch = nextch(); } int nr = 0; while(isdigit(ch)) { nr = nr * 10 + ch - '0'; ch = nextch(); } return nr; } const int MAXN = (int) 5e5; vector <int> g[MAXN + 1]; pair <int, int> edges[MAXN + 1]; bool vis[MAXN + 1], vis1[MAXN + 1]; vector <int> ord; void dfs(int nod) { while(g[nod].size()) { auto it = g[nod].back(); g[nod].pop_back(); if(vis[it] == 0) { vis[it] = 1; dfs(edges[it].first ^ edges[it].second ^ nod); } } ord.push_back(nod); } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, m; //ios::sync_with_stdio(false); //cin.tie(0), cout.tie(0); n = getnr(); m = getnr(); for(i = 1; i <= m; i++) { int x, y; x = getnr(); y = getnr(); edges[i] = {x, y}; g[x].push_back(i); g[y].push_back(i); } dfs(1); int sz = ord.size(); vector <int> stk; for(i = 0; i < sz; i++) { if(vis1[ord[i]] == 0) { vis1[ord[i]] = 1; stk.push_back(ord[i]); } else { while(stk.back() != ord[i]) { printf("%d " ,stk.back()); vis1[stk.back()] = 0; stk.pop_back(); } printf("%d " ,ord[i]); } } //cout << ans; //cin.close(); //cout.close(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12136 KB | Output is correct |
2 | Incorrect | 12 ms | 12032 KB | Edge does not exist or used 4, 2 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 12028 KB | Output is correct |
2 | Incorrect | 13 ms | 12032 KB | Edge does not exist or used 4, 2 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12032 KB | Output is correct |
2 | Incorrect | 14 ms | 12084 KB | Edge does not exist or used 4, 2 |
3 | Halted | 0 ms | 0 KB | - |