Submission #261226

#	Time	Username	Problem	Language	Result	Execution time	Memory
261226		eohomegrownapps	Senior Postmen (BOI14_postmen)	C++14	55 / 100	761 ms	111920 KiB

postmen

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

int tarr[500000];
int ptr = 0;
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 (ptr>0&&tarr[ptr-1]!=i){
            cout<<tarr[ptr-1]+1<<' ';
            visited[tarr[ptr-1]]=false;
            ptr--;
        }
        cout<<'\n';
    } else {
        visited[i]=true;
        ptr++;
        tarr[ptr-1]=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