oj.uz

Submission #11581

# Submission time Handle Problem Language Result Execution time Memory
11581 2014-12-02T14:49:52 Z gs14004 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 99716 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 21 ms 27776 KB Output is correct
2 Correct 28 ms 27648 KB Output is correct
3 Correct 22 ms 27776 KB Output is correct
4 Correct 33 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 41 ms 29440 KB Output is correct
8 Correct 24 ms 28032 KB Output is correct
9 Correct 147 ms 39544 KB Output is correct
10 Correct 33 ms 28032 KB Output is correct
11 Correct 26 ms 28032 KB Output is correct
12 Correct 196 ms 39856 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 27752 KB Output is correct
2 Correct 22 ms 27776 KB Output is correct
3 Correct 27 ms 27776 KB Output is correct
4 Correct 27 ms 28160 KB Output is correct
5 Correct 28 ms 27776 KB Output is correct
6 Correct 27 ms 28288 KB Output is correct
7 Correct 34 ms 29432 KB Output is correct
8 Correct 29 ms 28008 KB Output is correct
9 Correct 131 ms 39544 KB Output is correct
10 Correct 31 ms 28032 KB Output is correct
11 Correct 26 ms 27984 KB Output is correct
12 Correct 176 ms 39780 KB Output is correct
13 Correct 170 ms 42064 KB Output is correct
14 Correct 170 ms 40412 KB Output is correct
15 Correct 161 ms 41608 KB Output is correct
16 Correct 157 ms 42052 KB Output is correct
17 Correct 186 ms 38644 KB Output is correct
18 Correct 187 ms 41336 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27752 KB Output is correct
2 Correct 22 ms 27776 KB Output is correct
3 Correct 28 ms 27776 KB Output is correct
4 Correct 26 ms 28160 KB Output is correct
5 Correct 22 ms 27904 KB Output is correct
6 Correct 25 ms 28288 KB Output is correct
7 Correct 42 ms 29432 KB Output is correct
8 Correct 24 ms 28032 KB Output is correct
9 Correct 147 ms 39608 KB Output is correct
10 Correct 28 ms 28024 KB Output is correct
11 Correct 28 ms 28032 KB Output is correct
12 Correct 194 ms 39796 KB Output is correct
13 Correct 171 ms 42188 KB Output is correct
14 Correct 178 ms 40404 KB Output is correct
15 Correct 180 ms 41608 KB Output is correct
16 Correct 167 ms 42044 KB Output is correct
17 Correct 178 ms 38656 KB Output is correct
18 Correct 194 ms 41376 KB Output is correct
19 Execution timed out 794 ms 99716 KB Time limit exceeded
20 Halted 0 ms 0 KB -