Submission #1172507

#TimeUsernameProblemLanguageResultExecution timeMemory
1172507VovamatrixSenior Postmen (BOI14_postmen)C++20
100 / 100
223 ms77908 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define PI acos(-1) #define LSB(i) ((i) & -(i)) #define ll long long #define pb push_back #define mp make_pair #define mt make_tuple #define fi first #define sc second #define th third #define fo fourth #define pii pair<int,int> #define pll pair<ll,ll> #define ldb double #define INF 1e15 #define MOD 1000000007 #define endl "\n" #define all(data) data.begin(),data.end() #define TYPEMAX(type) std::numeric_limits<type>::max() #define TYPEMIN(type) std::numeric_limits<type>::min() #define MAXN 500007 vector<pll> adj[MAXN]; vector<ll> et; bool vis[MAXN],vise[MAXN]; ll lst[MAXN]; void DFS(ll u) { vis[u]=true; while(!adj[u].empty()) { pll vw=adj[u].back(); adj[u].pop_back(); ll v=vw.fi,w=vw.sc; if(vise[w]) continue; vise[w]=true; DFS(v); } et.pb(u); } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n,m,u,v; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u>>v; adj[u].pb({v,i}); adj[v].pb({u,i}); } for(int i=1;i<=n;i++) { if(!vis[i]) DFS(i); } for(int i=1;i<=n;i++) lst[i]=-1; stack<ll> st; for(int i=0;i<et.size();i++) { ll u=et[i]; if(lst[u]==-1) {lst[u]=i; st.push(u);} else { cout<<u<<" "; while(lst[st.top()]>lst[u]) {cout<<st.top()<<" "; lst[st.top()]=-1; st.pop();} cout<<endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...