Submission #261224

#	Time	Username	Problem	Language	Result	Execution time	Memory
261224		eohomegrownapps	Senior Postmen (BOI14_postmen)	C++14	55 / 100	1010 ms	110456 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

stack<int> proc;
bool visited[500000];
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);
    }
    int i = node;
    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);
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for (int i = 0; i<n; i++){
        visited[i]=0;
    }
    //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);
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45