oj.uz

Submission #11582

# Submission time Handle Problem Language Result Execution time Memory
11582 2014-12-02T14:50:06 Z gs14004 Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 99712 KB 
#include <cstdio>
#include <vector>
#include <cstring>
#include <unordered_set>
using namespace std;

unordered_set<int> graph[500005];

int n,m;

vector<int> cyc, temp;

void f(int x){
    unordered_set<int> ::iterator it;
    while (graph[x].size()) {
        it = graph[x].begin();
        int pos = *it;
        graph[x].erase(it);
        graph[pos].erase(graph[pos].find(x));
        f(pos);
    }
    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);
        graph[s].insert(e);
        graph[e].insert(s);
    }
    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:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<cyc.size(); i++) {
                   ~^~~~~~~~~~~
postmen.cpp:27: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:30: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 24 ms 27648 KB Output is correct
2 Correct 23 ms 27648 KB Output is correct
3 Correct 24 ms 27776 KB Output is correct
4 Correct 33 ms 28160 KB Output is correct
5 Correct 24 ms 27776 KB Output is correct
6 Correct 26 ms 28288 KB Output is correct
7 Correct 33 ms 29440 KB Output is correct
8 Correct 27 ms 28008 KB Output is correct
9 Correct 140 ms 39672 KB Output is correct
10 Correct 24 ms 28032 KB Output is correct
11 Correct 23 ms 28032 KB Output is correct
12 Correct 150 ms 39800 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 27648 KB Output is correct
2 Correct 22 ms 27752 KB Output is correct
3 Correct 27 ms 27792 KB Output is correct
4 Correct 24 ms 28160 KB Output is correct
5 Correct 25 ms 27776 KB Output is correct
6 Correct 25 ms 28288 KB Output is correct
7 Correct 34 ms 29432 KB Output is correct
8 Correct 25 ms 28032 KB Output is correct
9 Correct 132 ms 39544 KB Output is correct
10 Correct 23 ms 28032 KB Output is correct
11 Correct 29 ms 28072 KB Output is correct
12 Correct 157 ms 39776 KB Output is correct
13 Correct 152 ms 42116 KB Output is correct
14 Correct 163 ms 40304 KB Output is correct
15 Correct 171 ms 41708 KB Output is correct
16 Correct 158 ms 42140 KB Output is correct
17 Correct 189 ms 38612 KB Output is correct
18 Correct 174 ms 41272 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27648 KB Output is correct
2 Correct 21 ms 27648 KB Output is correct
3 Correct 23 ms 27784 KB Output is correct
4 Correct 34 ms 28160 KB Output is correct
5 Correct 27 ms 27904 KB Output is correct
6 Correct 25 ms 28288 KB Output is correct
7 Correct 33 ms 29440 KB Output is correct
8 Correct 35 ms 28024 KB Output is correct
9 Correct 158 ms 39672 KB Output is correct
10 Correct 24 ms 28032 KB Output is correct
11 Correct 33 ms 28100 KB Output is correct
12 Correct 171 ms 39744 KB Output is correct
13 Correct 161 ms 42104 KB Output is correct
14 Correct 188 ms 40408 KB Output is correct
15 Correct 181 ms 41692 KB Output is correct
16 Correct 176 ms 42076 KB Output is correct
17 Correct 184 ms 38708 KB Output is correct
18 Correct 178 ms 41328 KB Output is correct
19 Execution timed out 806 ms 99712 KB Time limit exceeded
20 Halted 0 ms 0 KB -