Submission #31560

#	Time	Username	Problem	Language	Result	Execution time	Memory
31560		Dat160601	Senior Postmen (BOI14_postmen)	C++14	100 / 100	358 ms	25368 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],cnt=0,ed[1000007],to[1000007],last[1000007],pre[1000007];
stack <int> res;
vector <int> ans;
inline void addedge(int u,int v,int i){
    cnt++;
    to[cnt]=v;
    ed[cnt]=i;
    pre[cnt]=last[u];
    last[u]=cnt;
    cnt++;
    to[cnt]=u;
    ed[cnt]=i;
    pre[cnt]=last[v];
    last[v]=cnt;
}
inline void dfs(int k){
    stack <int> st;
    st.push(k);
    while(!st.empty()){
        int u=st.top(),ok=0;
        for(int i=last[u];i;i=pre[i]){
            int v=to[i];
            int id=ed[i];
            last[u]=pre[i];
            if(vis[id]==1) continue;
            vis[id]=1;
            ok=1;
            st.push(v);
            break;
        }
        if(!ok){
            ans.pb(u);
            st.pop();
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        addedge(u,v,i);
    }
    dfs(1);
    stack <int> stl;
    for(int i=0;i<(int)ans.size();i++){
        u=ans[i];
        if(hav[u]){
            while(!stl.empty() && stl.top()!=u){
                printf("%d ",stl.top());
                hav[stl.top()]=0;
                stl.pop();
            }
            printf("%d\n",u);
        }
        else{
            hav[u]=1;
            stl.push(u);
        }
    }
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
postmen.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~

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