Submission #136388

#TimeUsernameProblemLanguageResultExecution timeMemory
136388tdwnSenior Postmen (BOI14_postmen)C++17
100 / 100
450 ms82576 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define pf push_front #define mp make_pair using namespace std; const int maxn = 500100; int in() { char c=getchar_unlocked(); while(c<'0'||c>'9') c=getchar_unlocked(); int r=0; while(c>='0'&&c<='9') { r=r*10+c-'0'; c=getchar_unlocked(); } return r; } void out(int x) { int lz=0, r=0; while(x%10==0) { ++lz; x/=10; } while(x) { r=r*10+x%10; x/=10; } while(r) { putchar_unlocked('0'+r%10); r/=10; } while(lz--) putchar_unlocked('0'); } class edge { public: int nxt_node; list<edge>::iterator reverse_edge; edge(int _node) { nxt_node = _node; } }; list<edge>adj[maxn]; int n, m; vector<int>euler_tour; bool visited[maxn]; void solve(int node) { while(adj[node].size() > 0) { edge x = adj[node].front(); int nxt = x.nxt_node; adj[nxt].erase(x.reverse_edge); adj[node].pop_front(); solve(nxt); } euler_tour.pb(node); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); n = in(); m = in(); int a, b; for(int i=0;i<m;i++) { a = in(); b = in(); adj[a].pf(edge(b)); list<edge>::iterator it_a = adj[a].begin(); adj[b].pf(edge(a)); list<edge>::iterator it_b = adj[b].begin(); it_a->reverse_edge = it_b; it_b->reverse_edge = it_a; } solve(1); vector<int>seq; for(int i:euler_tour) { //cout<<i<<" "; if(!visited[i]) { seq.pb(i); visited[i] = true; } else { // go back in seq while you find i while(seq.size() > 0 && seq.back() != i) { visited[seq.back()] = false; out(seq.back()); putchar_unlocked(' '); seq.pop_back(); } out(i); putchar_unlocked('\n'); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...