oj.uz

Submission #11588

# Submission time Handle Problem Language Result Execution time Memory
11588 2014-12-02T16:31:26 Z gs14004 Senior Postmen (BOI14_postmen) C++
38 / 100
 500 ms 7768 KB 
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
 
int n,m;
int st[1000005], con[1000005], link[1000005], v[500005], sz;
 
vector<int> cyc, temp;
 
void add_edge(int s, int e){
    sz++;
    link[sz] = e; con[sz] = st[s]; st[s] = sz;
    sz++;
    link[sz] = s; con[sz] = st[e]; st[e] = sz;
}
 
void f(int x){
    int p = st[x];
    while (p) {
        int pos = link[p];
        int q = (p+1)/2;
        if(!v[q]){
            v[q]=1;
            f(pos);
        }
        st[x] = p = con[p];
    }
    cyc.push_back(x);
}
 
int vis[500005];
int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        int s,e;
        scanf("%d %d",&s,&e);
        add_edge(s,e);
    }
    f(1);
    for (int i=0; i<cyc.size(); i++) {
        temp.push_back(cyc[i]);
        if(vis[cyc[i]]){
            printf("%d",temp.back());
            temp.pop_back();
            while(temp.back() != cyc[i]){
                printf(" %d",temp.back());
                vis[temp.back()] = 0;
                temp.pop_back();
                if(temp.back() == cyc[i]) printf("\n");
            }
        }
        else vis[cyc[i]] = 1;
    }
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<cyc.size(); i++) {
                   ~^~~~~~~~~~~
postmen.cpp:34: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:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&s,&e);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 360 KB Output is correct
4 Correct 11 ms 560 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 24 ms 1280 KB Output is correct
8 Correct 6 ms 488 KB Output is correct
9 Correct 313 ms 6260 KB Output is correct
10 Correct 6 ms 560 KB Output is correct
11 Correct 6 ms 488 KB Output is correct
12 Correct 114 ms 6392 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 18 ms 1280 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 310 ms 6300 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 113 ms 6380 KB Output is correct
13 Correct 62 ms 7768 KB Output is correct
14 Correct 58 ms 5848 KB Output is correct
15 Execution timed out 1081 ms 6108 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 9 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 11 ms 640 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 309 ms 6332 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 114 ms 6464 KB Output is correct
13 Correct 57 ms 7664 KB Output is correct
14 Correct 56 ms 5896 KB Output is correct
15 Execution timed out 1085 ms 6168 KB Time limit exceeded
16 Halted 0 ms 0 KB -