Submission #261217

#	Time	Username	Problem	Language	Result	Execution time	Memory
261217		eohomegrownapps	Senior Postmen (BOI14_postmen)	C++14	55 / 100	715 ms	93180 KiB

postmen

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

vector<int> eulertour;
vector<set<int>> adjlist;

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.push_back(node);
}

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;
    vector<bool> visited(n);
    for (int i : eulertour){
        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