oj.uz

Submission #261222

# Submission time Handle Problem Language Result Execution time Memory
261222 2020-08-11T14:53:08 Z eohomegrownapps Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 96248 KB 
#include <bits/stdc++.h>
using namespace std;

int eulertour[1000000];
int ptr = 0;
unordered_set<int> adjlist[500000];

inline void deleteEdge(int a, int b){
    adjlist[a].erase(b);
    adjlist[b].erase(a);
}
void tour(int node){
    while (adjlist[node].size()>0){
        int newnode = *adjlist[node].begin();
        deleteEdge(node, newnode);
        tour(newnode);
    }
    eulertour[ptr]=node;
    ptr++;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    //adjlist.resize(n);
    for (int i = 0; i<m; i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        adjlist[a].insert(b);
        adjlist[b].insert(a);
    }
    tour(0);
    stack<int> proc;
    bool visited[500000];
    for (int i = 0; i<n; i++){
        visited[i]=0;
    }
    for (int ix = 0; ix<ptr; ix++){
        int i = eulertour[ix];
        if (visited[i]){
            cout<<i+1<<' ';
            while (proc.size()>0&&proc.top()!=i){
                cout<<proc.top()+1<<' ';
                visited[proc.top()]=false;
                proc.pop();
            }
            cout<<'\n';
        } else {
            visited[i]=true;
            proc.push(i);
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 27776 KB Output is correct
2 Correct 23 ms 27776 KB Output is correct
3 Correct 20 ms 27776 KB Output is correct
4 Correct 24 ms 28160 KB Output is correct
5 Correct 26 ms 27904 KB Output is correct
6 Correct 30 ms 28288 KB Output is correct
7 Correct 36 ms 29568 KB Output is correct
8 Correct 22 ms 28032 KB Output is correct
9 Correct 128 ms 40440 KB Output is correct
10 Correct 24 ms 28024 KB Output is correct
11 Correct 27 ms 28152 KB Output is correct
12 Correct 143 ms 40696 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27776 KB Output is correct
2 Correct 21 ms 27724 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 23 ms 28160 KB Output is correct
5 Correct 21 ms 27904 KB Output is correct
6 Correct 25 ms 28288 KB Output is correct
7 Correct 33 ms 29568 KB Output is correct
8 Correct 22 ms 28032 KB Output is correct
9 Correct 125 ms 40440 KB Output is correct
10 Correct 25 ms 28032 KB Output is correct
11 Correct 27 ms 28032 KB Output is correct
12 Correct 149 ms 40696 KB Output is correct
13 Correct 167 ms 41336 KB Output is correct
14 Correct 172 ms 39764 KB Output is correct
15 Correct 175 ms 41096 KB Output is correct
16 Correct 183 ms 41340 KB Output is correct
17 Correct 190 ms 38392 KB Output is correct
18 Correct 199 ms 40940 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27904 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 21 ms 27904 KB Output is correct
4 Correct 24 ms 28160 KB Output is correct
5 Correct 22 ms 27904 KB Output is correct
6 Correct 24 ms 28288 KB Output is correct
7 Correct 32 ms 29560 KB Output is correct
8 Correct 22 ms 28032 KB Output is correct
9 Correct 141 ms 40440 KB Output is correct
10 Correct 25 ms 28032 KB Output is correct
11 Correct 23 ms 28032 KB Output is correct
12 Correct 145 ms 40700 KB Output is correct
13 Correct 179 ms 41344 KB Output is correct
14 Correct 168 ms 39800 KB Output is correct
15 Correct 167 ms 41096 KB Output is correct
16 Correct 170 ms 41336 KB Output is correct
17 Correct 169 ms 38520 KB Output is correct
18 Correct 147 ms 40952 KB Output is correct
19 Execution timed out 747 ms 96248 KB Time limit exceeded
20 Halted 0 ms 0 KB -