Submission #1221240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221240		vanea	Senior Postmen (BOI14_postmen)	C++20	0 / 100	11 ms	23880 KiB

postmen

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

const int mxN = 5e5+10;

set<int> rem;
set<int> adj[mxN];
int last[mxN], now = 0, beg;

void dfs(int node) {
    if(adj[node].size() == 0) return;
    cout << node << ' ';
    last[node] = now;
    int nxt = -1;
    for(auto it : adj[node]) {
        if(it == beg) {
            nxt = beg; break;
        }
        if(last[it] == now) continue;
        nxt = it;
    }
    if(nxt == -1) {
        while(1) {}
    }
    adj[node].erase(nxt);
    if(adj[node].size() == 0) rem.erase(node);
    adj[nxt].erase(node);
    if(adj[nxt].size() == 0) rem.erase(nxt);
    dfs(nxt);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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);
    }
    for(int i = 1; i <= n; i++) rem.insert(i);
    while(!rem.empty()) {
        int node = *rem.begin();
        ++now; beg = node;
        dfs(node);
        cout << '\n';
    }
}

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