oj.uz

Submission #11579

# Submission time Handle Problem Language Result Execution time Memory
11579 2014-12-02T14:44:20 Z gs14004 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 94276 KB 
#include <cstdio>
#include <vector>
#include <cstring>
#include <set>
using namespace std;

set<int> graph[500005];

int n,m;

vector<int> cyc, temp;

void f(int x){
    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 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23828 KB Output is correct
4 Correct 28 ms 24192 KB Output is correct
5 Correct 23 ms 23992 KB Output is correct
6 Correct 27 ms 24448 KB Output is correct
7 Correct 37 ms 25892 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 198 ms 37756 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 25 ms 24096 KB Output is correct
12 Correct 188 ms 37856 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23720 KB Output is correct
2 Correct 21 ms 23732 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 24 ms 24184 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 22 ms 24424 KB Output is correct
7 Correct 37 ms 25864 KB Output is correct
8 Correct 23 ms 24144 KB Output is correct
9 Correct 199 ms 37824 KB Output is correct
10 Correct 22 ms 24168 KB Output is correct
11 Correct 27 ms 24040 KB Output is correct
12 Correct 180 ms 37880 KB Output is correct
13 Correct 149 ms 37912 KB Output is correct
14 Correct 144 ms 37844 KB Output is correct
15 Correct 153 ms 37856 KB Output is correct
16 Correct 140 ms 37912 KB Output is correct
17 Correct 162 ms 37880 KB Output is correct
18 Correct 147 ms 35160 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 22 ms 24168 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 21 ms 24424 KB Output is correct
7 Correct 37 ms 25848 KB Output is correct
8 Correct 24 ms 24076 KB Output is correct
9 Correct 223 ms 37856 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Correct 227 ms 37804 KB Output is correct
13 Correct 151 ms 37876 KB Output is correct
14 Correct 156 ms 37884 KB Output is correct
15 Correct 190 ms 37836 KB Output is correct
16 Correct 130 ms 37856 KB Output is correct
17 Correct 169 ms 37856 KB Output is correct
18 Correct 141 ms 35184 KB Output is correct
19 Execution timed out 685 ms 94276 KB Time limit exceeded
20 Halted 0 ms 0 KB -