oj.uz

Submission #11211

# Submission time Handle Problem Language Result Execution time Memory
11211 2014-11-19T00:01:18 Z gs14004 Senior Postmen (BOI14_postmen) C++
55 / 100
 500 ms 94340 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();
            }
            puts("");
        }
        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 20 ms 23808 KB Output is correct
3 Correct 24 ms 23836 KB Output is correct
4 Correct 24 ms 24244 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 27 ms 24448 KB Output is correct
7 Correct 41 ms 25888 KB Output is correct
8 Correct 24 ms 24064 KB Output is correct
9 Correct 203 ms 37756 KB Output is correct
10 Correct 24 ms 24164 KB Output is correct
11 Correct 22 ms 24064 KB Output is correct
12 Correct 203 ms 37952 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 21 ms 23816 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 23 ms 24192 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 26 ms 24448 KB Output is correct
7 Correct 34 ms 25824 KB Output is correct
8 Correct 23 ms 24040 KB Output is correct
9 Correct 193 ms 37880 KB Output is correct
10 Correct 19 ms 24192 KB Output is correct
11 Correct 27 ms 24188 KB Output is correct
12 Correct 184 ms 37892 KB Output is correct
13 Correct 136 ms 37884 KB Output is correct
14 Correct 137 ms 37880 KB Output is correct
15 Correct 155 ms 37984 KB Output is correct
16 Correct 156 ms 37904 KB Output is correct
17 Correct 165 ms 37880 KB Output is correct
18 Correct 149 ms 35260 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 20 ms 24192 KB Output is correct
5 Correct 31 ms 23936 KB Output is correct
6 Correct 23 ms 24448 KB Output is correct
7 Correct 32 ms 25856 KB Output is correct
8 Correct 36 ms 24056 KB Output is correct
9 Correct 198 ms 37856 KB Output is correct
10 Correct 23 ms 24192 KB Output is correct
11 Correct 20 ms 24192 KB Output is correct
12 Correct 186 ms 37880 KB Output is correct
13 Correct 147 ms 37804 KB Output is correct
14 Correct 136 ms 37856 KB Output is correct
15 Correct 155 ms 37880 KB Output is correct
16 Correct 134 ms 37880 KB Output is correct
17 Correct 166 ms 37856 KB Output is correct
18 Correct 194 ms 35184 KB Output is correct
19 Execution timed out 716 ms 94340 KB Time limit exceeded
20 Halted 0 ms 0 KB -