Submission #775512

#	Time	Username	Problem	Language	Result	Execution time	Memory
775512		MEGalodon	Senior Postmen (BOI14_postmen)	C++17	55 / 100	536 ms	111396 KiB

postmen

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