oj.uz

Submission #11214

# Submission time Handle Problem Language Result Execution time Memory
11214 2014-11-19T01:15:53 Z gs14004 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 94280 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();
            }
            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 22 ms 23808 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 25 ms 24192 KB Output is correct
5 Correct 24 ms 23992 KB Output is correct
6 Correct 28 ms 24448 KB Output is correct
7 Correct 33 ms 25856 KB Output is correct
8 Correct 26 ms 24064 KB Output is correct
9 Correct 204 ms 37808 KB Output is correct
10 Correct 24 ms 24348 KB Output is correct
11 Correct 23 ms 24064 KB Output is correct
12 Correct 190 ms 37856 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 21 ms 23808 KB Output is correct
4 Correct 20 ms 24244 KB Output is correct
5 Correct 25 ms 23936 KB Output is correct
6 Correct 29 ms 24448 KB Output is correct
7 Correct 35 ms 25856 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 207 ms 37804 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 23 ms 24064 KB Output is correct
12 Correct 192 ms 37856 KB Output is correct
13 Correct 125 ms 37880 KB Output is correct
14 Correct 155 ms 37856 KB Output is correct
15 Correct 166 ms 37916 KB Output is correct
16 Correct 146 ms 37864 KB Output is correct
17 Correct 183 ms 37852 KB Output is correct
18 Correct 145 ms 35116 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 22 ms 23784 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 23 ms 24192 KB Output is correct
5 Correct 19 ms 23912 KB Output is correct
6 Correct 25 ms 24448 KB Output is correct
7 Correct 34 ms 25824 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 203 ms 37872 KB Output is correct
10 Correct 22 ms 24192 KB Output is correct
11 Correct 23 ms 24144 KB Output is correct
12 Correct 187 ms 37820 KB Output is correct
13 Correct 134 ms 37988 KB Output is correct
14 Correct 134 ms 37800 KB Output is correct
15 Correct 178 ms 37824 KB Output is correct
16 Correct 134 ms 37864 KB Output is correct
17 Correct 171 ms 37884 KB Output is correct
18 Correct 152 ms 35160 KB Output is correct
19 Execution timed out 702 ms 94280 KB Time limit exceeded
20 Halted 0 ms 0 KB -