# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
881082 | 2023-11-30T14:24:26 Z | Requiem | Senior Postmen (BOI14_postmen) | C++17 | 6 ms | 17084 KB |
#include<bits/stdc++.h> #define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define INF 1e18 #define fi first #define se second #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define endl '\n' #define pi 3.14159265359 #define TASKNAME "postmen" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 5e5 + 9; vector<int> g[MAXN]; int n,m; bool used[MAXN]; ii edge[MAXN]; list<int> euler_circuit(int u){ list<int> ans; int v; ans.pb(u); while(!g[u].empty()){ int id = g[u].back(); g[u].pop_back(); if (used[id]) continue; v = edge[id].fi + edge[id].se - u; used[id] = true; u = v; ans.pb(u); } auto it = ans.begin(); it++; for(; it != ans.end(); it++){ list<int> vert = euler_circuit(*it); vert.pop_front(); ans.splice(it,vert); } return ans; } bool inqueue[MAXN]; main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>edge[i].fi>>edge[i].se; g[edge[i].fi].pb(i); g[edge[i].se].pb(i); } memset(used,false,sizeof(used)); list<int> ans = euler_circuit(1); stack<int> st; memset(inqueue,false,sizeof(inqueue)); // for(auto x: ans){ // cout<<x<<' '; // } // cout<<endl; for(auto x: ans){ if (!inqueue[x]){ inqueue[x] = true; st.push(x); } else{ cout<<x<<' '; while(!st.empty() and st.top() != x){ cout<<st.top()<<' '; inqueue[st.top()] = false; st.pop(); } cout<<endl; } } cout<<endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 16728 KB | Output is correct |
2 | Correct | 4 ms | 16732 KB | Output is correct |
3 | Correct | 4 ms | 16732 KB | Output is correct |
4 | Correct | 4 ms | 16988 KB | Output is correct |
5 | Incorrect | 4 ms | 16732 KB | Edge does not exist or used 32, 2 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 16732 KB | Output is correct |
2 | Correct | 3 ms | 16728 KB | Output is correct |
3 | Correct | 4 ms | 16728 KB | Output is correct |
4 | Correct | 6 ms | 16984 KB | Output is correct |
5 | Incorrect | 4 ms | 16988 KB | Edge does not exist or used 32, 2 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 16732 KB | Output is correct |
2 | Correct | 3 ms | 16728 KB | Output is correct |
3 | Correct | 4 ms | 16732 KB | Output is correct |
4 | Correct | 5 ms | 17084 KB | Output is correct |
5 | Incorrect | 4 ms | 16732 KB | Edge does not exist or used 32, 2 |
6 | Halted | 0 ms | 0 KB | - |