Submission #775503

#	Time	Username	Problem	Language	Result	Execution time	Memory
775503		MEGalodon	Senior Postmen (BOI14_postmen)	C++14	55 / 100	110 ms	23624 KiB

postmen

#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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45