제출 #136361

#제출 시각아이디문제언어결과실행 시간메모리
136361tdwn어르신 집배원 (BOI14_postmen)C++17
55 / 100
886 ms82536 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; 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() { cin>>n>>m; int a, b; for(int i=0;i<m;i++) { cin>>a>>b; 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) { if(!visited[i]) { seq.pb(i); visited[i] = true; } else { // go back in seq while you find i vector<int>v; while(seq.size() > 0 && seq.back() != i) { v.pb(seq.back()); visited[seq.back()] = false; seq.pop_back(); } v.pb(i); for(int i:v) { cout<<i<<" "; } cout<<"\n"; } } cout<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...