oj.uz

Submission #109018

# Submission time Handle Problem Language Result Execution time Memory
109018 2019-05-04T03:18:39 Z thebes Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 42360 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 5e5+5;
set<int> adj[MN];
int n, m, i, x, y, f, rt, st[MN];
stack<int> s;

void dfs(int n,int p){
    st[n]=1; s.push(n);
    for(auto v : adj[n]){
        if(v==p) continue;
        if(v==rt){
            adj[n].erase(rt);
            adj[rt].erase(n);
            int lst = n;
            printf("%d ",n);
            while(s.size()>1){
                s.pop();
                int cur = s.top();
                printf("%d ",cur);
                adj[cur].erase(lst);
                adj[lst].erase(cur);
                lst = cur;
            }
            printf("\n");
            f = 1;
        }
        else if(!st[v]) dfs(v,n);
        if(f) break;
    }
    st[n]=0;
    if(s.size()&&s.top()==n) s.pop();
}

int main(){
    for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        adj[x].insert(y);
        adj[y].insert(x);
    }
    i=1;
    while(i<=n){
        f=0; rt=i; dfs(i,-1);
        if(!f) i++;
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:37:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
postmen.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 23784 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 23 ms 24064 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 32 ms 25256 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 157 ms 33532 KB Output is correct
10 Correct 26 ms 24184 KB Output is correct
11 Correct 20 ms 24192 KB Output is correct
12 Correct 437 ms 33896 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 26 ms 24192 KB Output is correct
5 Correct 19 ms 24064 KB Output is correct
6 Correct 32 ms 24184 KB Output is correct
7 Correct 44 ms 25344 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 179 ms 33528 KB Output is correct
10 Correct 28 ms 24064 KB Output is correct
11 Correct 21 ms 24168 KB Output is correct
12 Correct 411 ms 33784 KB Output is correct
13 Correct 145 ms 42360 KB Output is correct
14 Execution timed out 1073 ms 37624 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 22 ms 23844 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 24 ms 24064 KB Output is correct
5 Correct 22 ms 23952 KB Output is correct
6 Correct 24 ms 24320 KB Output is correct
7 Correct 36 ms 25336 KB Output is correct
8 Correct 19 ms 24192 KB Output is correct
9 Correct 193 ms 33628 KB Output is correct
10 Correct 29 ms 24192 KB Output is correct
11 Correct 21 ms 24168 KB Output is correct
12 Correct 439 ms 33812 KB Output is correct
13 Correct 133 ms 42360 KB Output is correct
14 Execution timed out 1089 ms 37608 KB Time limit exceeded
15 Halted 0 ms 0 KB -