oj.uz

Submission #775503

# Submission time Handle Problem Language Result Execution time Memory
775503 2023-07-06T13:05:06 Z MEGalodon Senior Postmen (BOI14_postmen) C++14
55 / 100
 110 ms 23624 KB 
#include <bits/stdc++.h>
#include <set>
#define MAXN 100001
using namespace std;
set<int> adj_lst[MAXN];
vector<int> euler;
vector<int> str;
int check[MAXN];
vector<vector<int>> ans;
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(){
    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];
    }
    int poss = 1;
    for( int i{1} ; i <= nodes ; ++i ){
        //cout<<degree[i]<<" ";
        if( degree[i]%2 ){
            poss = 0;
        }
    } //cout<<'\n';
    //cout<<l<<" "<<r<<" "<<poss<<'\n';
    if( !poss ){
        cout<<"IMPOSSIBLE\n";
        return 0;
    }
    //adj_lst[l].insert(r); adj_lst[r].insert(l);
    find(1);
    for( int i{1} ; i <= nodes ; ++i ){
        if( (int)adj_lst[i].size() ){
            cout<<"IMPOSSIBLE\n";
            return 0;
        }
    }
    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';
            vector<int> nw;
            nw.push_back(u);
            while( curr.back() != u && !curr.empty() ) nw.push_back(curr.back()), check[curr.back()] = 0, curr.pop_back();
            //nw.push_back(u);
            ans.push_back(nw);
            //for( int x : nw ) cerr<<x<<" "; cerr<<'\n';
        }
        else{
            check[u] = 1;
            curr.push_back(u);
        }
    }
    for( vector<int> &sol : ans ){
        for( int x : sol ) cout<<x<<" ";
        cout<<'\n';
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 5 ms 5716 KB Output is correct
7 Correct 15 ms 7584 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 104 ms 22200 KB Output is correct
10 Correct 5 ms 5428 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 101 ms 22400 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 6 ms 5716 KB Output is correct
7 Correct 19 ms 7576 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 109 ms 22348 KB Output is correct
10 Correct 4 ms 5460 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 101 ms 22444 KB Output is correct
13 Correct 80 ms 23576 KB Output is correct
14 Correct 96 ms 23492 KB Output is correct
15 Correct 97 ms 23060 KB Output is correct
16 Correct 83 ms 23624 KB Output is correct
17 Correct 94 ms 23256 KB Output is correct
18 Correct 89 ms 18784 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 5 ms 5656 KB Output is correct
7 Correct 14 ms 7524 KB Output is correct
8 Correct 3 ms 5276 KB Output is correct
9 Correct 110 ms 22136 KB Output is correct
10 Correct 4 ms 5532 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 108 ms 22468 KB Output is correct
13 Correct 80 ms 23584 KB Output is correct
14 Correct 97 ms 23408 KB Output is correct
15 Correct 100 ms 22992 KB Output is correct
16 Correct 83 ms 23596 KB Output is correct
17 Correct 95 ms 23304 KB Output is correct
18 Correct 87 ms 18852 KB Output is correct
19 Runtime error 8 ms 9984 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -