oj.uz

Submission #775512

# Submission time Handle Problem Language Result Execution time Memory
775512 2023-07-06T13:10:45 Z MEGalodon Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 111396 KB 
#include <bits/stdc++.h>
#include <set>
#define MAXN 500001
using namespace std;
set<int> adj_lst[MAXN];
vector<int> euler;
vector<int> str;
int check[MAXN];
void find(int u){
    euler.push_back(u);
    //cerr<<u<<" ";
    while( (int)adj_lst[u].size() ){
        int x = *adj_lst[u].begin();
        adj_lst[u].erase(x);
        adj_lst[x].erase(u);
        find(x);
    }
    str.push_back(u);
    euler.pop_back();
}
int degree[MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int nodes, edges;
    cin>>nodes>>edges;
    while( edges-- ){
        int u, v;
        cin>>u>>v;
        adj_lst[u].insert(v);
        adj_lst[v].insert(u);
        ++degree[u]; ++degree[v];
    }
    //cout<<l<<" "<<r<<" "<<poss<<'\n';
    //adj_lst[l].insert(r); adj_lst[r].insert(l);
    find(1);
    vector<int> curr;
    //for( int i{(int)str.size()-1} ; i >= 0 ; --i ) cout<<str[i]<<" "; cout<<'\n';
    while( !str.empty() ){
        int u = str.back();
        str.pop_back();
        if( check[u] ){
            //cerr<<u<<'\n';
            cout<<u<<" ";
            while( curr.back() != u && !curr.empty() ) cout<<curr.back()<<" ", check[curr.back()] = 0, curr.pop_back();
            //nw.push_back(u);
            cout<<'\n';
            //for( int x : nw ) cerr<<x<<" "; cerr<<'\n';
        }
        else{
            check[u] = 1;
            curr.push_back(u);
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 11 ms 23784 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 10 ms 23892 KB Output is correct
6 Correct 12 ms 24532 KB Output is correct
7 Correct 19 ms 26328 KB Output is correct
8 Correct 11 ms 24148 KB Output is correct
9 Correct 91 ms 40296 KB Output is correct
10 Correct 12 ms 24404 KB Output is correct
11 Correct 11 ms 24148 KB Output is correct
12 Correct 77 ms 40432 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23820 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 11 ms 23784 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 10 ms 23892 KB Output is correct
6 Correct 13 ms 24580 KB Output is correct
7 Correct 19 ms 26308 KB Output is correct
8 Correct 11 ms 24148 KB Output is correct
9 Correct 82 ms 40284 KB Output is correct
10 Correct 12 ms 24300 KB Output is correct
11 Correct 11 ms 24148 KB Output is correct
12 Correct 78 ms 40468 KB Output is correct
13 Correct 59 ms 41268 KB Output is correct
14 Correct 60 ms 41192 KB Output is correct
15 Correct 69 ms 40904 KB Output is correct
16 Correct 59 ms 41288 KB Output is correct
17 Correct 72 ms 41004 KB Output is correct
18 Correct 56 ms 36556 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23820 KB Output is correct
3 Correct 10 ms 23760 KB Output is correct
4 Correct 11 ms 24276 KB Output is correct
5 Correct 10 ms 24012 KB Output is correct
6 Correct 13 ms 24584 KB Output is correct
7 Correct 23 ms 26272 KB Output is correct
8 Correct 11 ms 24096 KB Output is correct
9 Correct 80 ms 40312 KB Output is correct
10 Correct 11 ms 24324 KB Output is correct
11 Correct 12 ms 24148 KB Output is correct
12 Correct 87 ms 40472 KB Output is correct
13 Correct 67 ms 41300 KB Output is correct
14 Correct 60 ms 41120 KB Output is correct
15 Correct 68 ms 40968 KB Output is correct
16 Correct 59 ms 41368 KB Output is correct
17 Correct 81 ms 41008 KB Output is correct
18 Correct 57 ms 36548 KB Output is correct
19 Correct 433 ms 111396 KB Output is correct
20 Execution timed out 536 ms 110580 KB Time limit exceeded
21 Halted 0 ms 0 KB -