oj.uz

Submission #31535

# Submission time Handle Problem Language Result Execution time Memory
31535 2017-08-29T07:39:21 Z ngkan146 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 51808 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[1000005];
vector <edge> G[1000005];
bool visited[1000005];
int n,m;
int euler[1000005], eulersize;
int q[1000005], qsize;
void dfs(){
    q[qsize++] = 1;
    while(qsize){
        int u = q[qsize-1];
        bool mjk = 0;

        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;
            mjk = 1;
            visited[id] = 1;
            q[qsize++] = v;
            break;
        }

        if(mjk) continue;

        euler[eulersize++] = u;
        --qsize;
    }
}
int st[1000005], stsize;
bool used[1000005];
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();

    for(int i=0;i<eulersize;++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()':
postmen.cpp:19:21: 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:38: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:41: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 17 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 25 ms 23808 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 26 ms 24064 KB Output is correct
7 Correct 28 ms 24424 KB Output is correct
8 Correct 18 ms 23936 KB Output is correct
9 Correct 58 ms 27040 KB Output is correct
10 Correct 22 ms 24032 KB Output is correct
11 Correct 25 ms 23936 KB Output is correct
12 Correct 72 ms 27360 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 24 ms 23860 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 19 ms 24064 KB Output is correct
5 Correct 24 ms 23912 KB Output is correct
6 Correct 23 ms 24064 KB Output is correct
7 Correct 24 ms 24448 KB Output is correct
8 Correct 18 ms 23936 KB Output is correct
9 Correct 62 ms 27092 KB Output is correct
10 Correct 21 ms 23936 KB Output is correct
11 Correct 20 ms 24064 KB Output is correct
12 Correct 62 ms 27384 KB Output is correct
13 Correct 111 ms 29412 KB Output is correct
14 Correct 94 ms 28536 KB Output is correct
15 Correct 84 ms 28140 KB Output is correct
16 Correct 104 ms 29360 KB Output is correct
17 Correct 110 ms 28024 KB Output is correct
18 Correct 91 ms 28596 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23836 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 25 ms 23808 KB Output is correct
4 Correct 25 ms 23936 KB Output is correct
5 Correct 24 ms 23900 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 33 ms 24448 KB Output is correct
8 Correct 20 ms 23936 KB Output is correct
9 Correct 85 ms 27048 KB Output is correct
10 Correct 32 ms 23936 KB Output is correct
11 Correct 33 ms 23936 KB Output is correct
12 Correct 71 ms 27384 KB Output is correct
13 Correct 96 ms 29280 KB Output is correct
14 Correct 108 ms 28512 KB Output is correct
15 Correct 78 ms 28116 KB Output is correct
16 Correct 118 ms 29408 KB Output is correct
17 Correct 116 ms 28024 KB Output is correct
18 Correct 136 ms 28536 KB Output is correct
19 Execution timed out 646 ms 51808 KB Time limit exceeded
20 Halted 0 ms 0 KB -