oj.uz

Submission #31556

# Submission time Handle Problem Language Result Execution time Memory
31556 2017-08-29T09:12:21 Z Dat160601 Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 17476 KB 
#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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12136 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 16 ms 12288 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 18 ms 12288 KB Output is correct
7 Correct 24 ms 12800 KB Output is correct
8 Correct 13 ms 12264 KB Output is correct
9 Correct 132 ms 15492 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 73 ms 15812 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 13 ms 12136 KB Output is correct
3 Correct 12 ms 12032 KB Output is correct
4 Correct 19 ms 12340 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 17 ms 12276 KB Output is correct
7 Correct 24 ms 12812 KB Output is correct
8 Correct 15 ms 12288 KB Output is correct
9 Correct 141 ms 15516 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 97 ms 15812 KB Output is correct
13 Correct 88 ms 17428 KB Output is correct
14 Correct 75 ms 16988 KB Output is correct
15 Execution timed out 1091 ms 15700 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12136 KB Output is correct
2 Correct 13 ms 12136 KB Output is correct
3 Correct 12 ms 12136 KB Output is correct
4 Correct 16 ms 12288 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 15 ms 12340 KB Output is correct
7 Correct 27 ms 12748 KB Output is correct
8 Correct 15 ms 12288 KB Output is correct
9 Correct 140 ms 15516 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 86 ms 15788 KB Output is correct
13 Correct 87 ms 17476 KB Output is correct
14 Correct 93 ms 17012 KB Output is correct
15 Execution timed out 1085 ms 15852 KB Time limit exceeded
16 Halted 0 ms 0 KB -