Submission #31556

#	Time	Username	Problem	Language	Result	Execution time	Memory
31556		Dat160601	Senior Postmen (BOI14_postmen)	C++14	38 / 100	1091 ms	17476 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,u,v,m,vis[500007],hav[500007];
vector < pair<int,int> > edge[500007];
stack <int> res;
vector <int> ans;
void dfs(int k){
    stack <int> st;
    st.push(k);
    while(!st.empty()){
        int u=st.top(),ok=0;
        for(int i=0;i<(int)edge[u].size();i++){
            int v=edge[u][i].fi;
            int id=edge[u][i].se;
            if(vis[id]==1) continue;
            vis[id]=1;
            ok=1;
            st.push(v);
            break;
        }
        if(!ok){
            ans.pb(u);
            st.pop();
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        edge[u].pb(mp(v,i));
        edge[v].pb(mp(u,i));
    }
    dfs(1);
    stack <int> stl;
    int el=0;
    for(int i=0;i<(int)ans.size();i++){
        u=ans[i];
        if(hav[u]){
            if(el==1) cout<<"\n";
            while(!stl.empty() && stl.top()!=u){
                cout<<stl.top()<<" ";
                hav[stl.top()]=0;
                stl.pop();
            }
            cout<<u;
            el=1;
        }
        else{
            hav[u]=1;
            stl.push(u);
        }
    }
}

• Subtask 1: 38 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45