oj.uz

Submission #31526

# Submission time Handle Problem Language Result Execution time Memory
31526 2017-08-29T07:27:48 Z ngkan146 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 53804 KB 
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int v=0, id=0;
    edge(int v=0,int id=0):id(id),v(v){}
};
int ctrl[500005];
vector <edge> G[500005];
bool visited[500005];
int n,m;
vector <int> euler;
void dfs(int u){
    for(;ctrl[u]<G[u].size();++ctrl[u]){
        int v = G[u][ctrl[u]].v;
        int id = G[u][ctrl[u]].id;
        if (visited[id]) continue;
        visited[id] = 1;
        dfs(v);
    }
    euler.push_back(u);
}
int st[500005], stsize;
bool used[500005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].push_back(edge(y,i));
        G[y].push_back(edge(x,i));
    }

    dfs(1);

    for(int i=0;i<euler.size();++i){
        if (used[euler[i]]){
            while(st[stsize-1] != euler[i]){
                printf("%d ",st[stsize-1]);
                used[st[stsize-1]] = 0;
                --stsize;
            };
            printf("%d\n",euler[i]);
        }
        else{
            st[stsize++] = euler[i];
            used[euler[i]] = 1;
        }
    }
}

Compilation message

postmen.cpp: In constructor 'edge::edge(int, int)':
postmen.cpp:4:17: warning: 'edge::id' will be initialized after [-Wreorder]
     int v=0, id=0;
                 ^
postmen.cpp:4:11: warning:   'int edge::v' [-Wreorder]
     int v=0, id=0;
           ^
postmen.cpp:5:5: warning:   when initialized here [-Wreorder]
     edge(int v=0,int id=0):id(id),v(v){}
     ^~~~
postmen.cpp: In function 'void dfs(int)':
postmen.cpp:13:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;ctrl[u]<G[u].size();++ctrl[u]){
          ~~~~~~~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<euler.size();++i){
                 ~^~~~~~~~~~~~~
postmen.cpp:25: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:28: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 13 ms 12032 KB Output is correct
2 Correct 14 ms 12032 KB Output is correct
3 Correct 13 ms 12136 KB Output is correct
4 Correct 16 ms 12356 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 17 ms 12416 KB Output is correct
7 Correct 18 ms 13184 KB Output is correct
8 Correct 19 ms 12288 KB Output is correct
9 Correct 69 ms 18192 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Correct 14 ms 12288 KB Output is correct
12 Correct 70 ms 18524 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12032 KB Output is correct
2 Correct 12 ms 12032 KB Output is correct
3 Correct 12 ms 12128 KB Output is correct
4 Correct 16 ms 12264 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 13 ms 12456 KB Output is correct
7 Correct 31 ms 13176 KB Output is correct
8 Correct 14 ms 12288 KB Output is correct
9 Correct 61 ms 18196 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 60 ms 18548 KB Output is correct
13 Correct 97 ms 20444 KB Output is correct
14 Correct 108 ms 18292 KB Output is correct
15 Correct 81 ms 19692 KB Output is correct
16 Correct 110 ms 20404 KB Output is correct
17 Correct 113 ms 16756 KB Output is correct
18 Correct 94 ms 18908 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 13 ms 12288 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 15 ms 12468 KB Output is correct
7 Correct 19 ms 13184 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 61 ms 18172 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 60 ms 18516 KB Output is correct
13 Correct 98 ms 20416 KB Output is correct
14 Correct 92 ms 18292 KB Output is correct
15 Correct 77 ms 19668 KB Output is correct
16 Correct 106 ms 20468 KB Output is correct
17 Correct 95 ms 16732 KB Output is correct
18 Correct 91 ms 18932 KB Output is correct
19 Execution timed out 575 ms 53804 KB Time limit exceeded
20 Halted 0 ms 0 KB -