oj.uz

Submission #97097

# Submission time Handle Problem Language Result Execution time Memory
97097 2019-02-13T20:39:20 Z dalgerok Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 55308 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 5e5 + 5;


int n, m, x[N], y[N];
vector < int > g[N];
bool used[N];
vector < int > q;


void dfs(int v){
    while(!g[v].empty()){
        int num = g[v].back();
        g[v].pop_back();
        if(used[num]){
            continue;
        }
        used[num] = true;
        int to = (x[num] ^ v ^ y[num]);
        dfs(to);
    }
    q.push_back(v);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> y[i];
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
    dfs(1);
    memset(used, 0, sizeof(used));
    vector < int > s;
    for(auto it : q){
        if(!used[it]){
            used[it] = true;
            s.push_back(it);
        }
        else{
            while(s.back() != it){
                cout << s.back() << " ";
                used[s.back()] = false;
                s.pop_back();
            }
            cout << it << "\n";
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12672 KB Output is correct
2 Correct 12 ms 12672 KB Output is correct
3 Correct 12 ms 12544 KB Output is correct
4 Correct 14 ms 12800 KB Output is correct
5 Correct 12 ms 12672 KB Output is correct
6 Correct 17 ms 12928 KB Output is correct
7 Correct 18 ms 13568 KB Output is correct
8 Correct 13 ms 12800 KB Output is correct
9 Correct 49 ms 18416 KB Output is correct
10 Correct 14 ms 12800 KB Output is correct
11 Correct 13 ms 12800 KB Output is correct
12 Correct 54 ms 18640 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12544 KB Output is correct
2 Correct 13 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 15 ms 12832 KB Output is correct
5 Correct 13 ms 12672 KB Output is correct
6 Correct 16 ms 12928 KB Output is correct
7 Correct 17 ms 13568 KB Output is correct
8 Correct 16 ms 12800 KB Output is correct
9 Correct 51 ms 18360 KB Output is correct
10 Correct 19 ms 12800 KB Output is correct
11 Correct 13 ms 12800 KB Output is correct
12 Correct 59 ms 18720 KB Output is correct
13 Correct 92 ms 21104 KB Output is correct
14 Correct 77 ms 18672 KB Output is correct
15 Correct 75 ms 19824 KB Output is correct
16 Correct 86 ms 21148 KB Output is correct
17 Correct 81 ms 17012 KB Output is correct
18 Correct 93 ms 19388 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12544 KB Output is correct
2 Correct 15 ms 12544 KB Output is correct
3 Correct 15 ms 12544 KB Output is correct
4 Correct 12 ms 12800 KB Output is correct
5 Correct 15 ms 12672 KB Output is correct
6 Correct 19 ms 12928 KB Output is correct
7 Correct 22 ms 13568 KB Output is correct
8 Correct 15 ms 12800 KB Output is correct
9 Correct 44 ms 18416 KB Output is correct
10 Correct 13 ms 12800 KB Output is correct
11 Correct 14 ms 12800 KB Output is correct
12 Correct 47 ms 18628 KB Output is correct
13 Correct 92 ms 21184 KB Output is correct
14 Correct 94 ms 18776 KB Output is correct
15 Correct 107 ms 19860 KB Output is correct
16 Correct 95 ms 21180 KB Output is correct
17 Correct 91 ms 17028 KB Output is correct
18 Correct 86 ms 19312 KB Output is correct
19 Execution timed out 575 ms 55308 KB Time limit exceeded
20 Halted 0 ms 0 KB -