Submission #704183

#	Time	Username	Problem	Language	Result	Execution time	Memory
704183		boyliguanhan	Senior Postmen (BOI14_postmen)	C++17	55 / 100	657 ms	151676 KiB

postmen

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
unordered_set<int> adj[500100];
int deg[500100];
stack<int> sol;
void reverse(){
    stack<int> temp;
    while(sol.size())
        temp.push(sol.top()), sol.pop();
    sol = temp;
}
void print(){
    stack<int> now;
    bitset<500100> appeared;
    while(sol.size()){
        if(appeared[sol.top()]){
            cout << sol.top() << ' ';
            while(now.top()!=sol.top())
                cout << now.top() << ' ', appeared[now.top()] = 0, now.pop();
            cout << '\n';
        } else {
            appeared[sol.top()] = 1;
            now.push(sol.top());
        }
        sol.pop();
    }
}
void dfs(int n){
    while(adj[n].size()){
        int i = *adj[n].begin();
        adj[n].erase(i);
        adj[i].erase(n);
        dfs(i);
    }
    sol.push(n);
}
int main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cout.sync_with_stdio(false);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
        adj[b].insert(a);
        deg[a]++;
        deg[b]++;
    }
    dfs(1);
    reverse();
    print();
    return 0;
}

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