Submission #261222

#	Time	Username	Problem	Language	Result	Execution time	Memory
261222		eohomegrownapps	Senior Postmen (BOI14_postmen)	C++14	55 / 100	747 ms	96248 KiB

postmen

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