Submission #1203319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203319		Hanksburger	Senior Postmen (BOI14_postmen)	C++20	100 / 100	176 ms	62648 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > s[500005];
int bad[500005], inb[500005];
vector<int> a, b;
void dfs(int u)
{
    while (s[u].size())
    {
        int v=s[u].back().first, w=s[u].back().second;
        s[u].pop_back();
        if (bad[w])
            continue;
        bad[w]=1;
        dfs(v);
    }
    a.push_back(u);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int u, v;
        cin >> u >> v;
        s[u].push_back({v, i});
        s[v].push_back({u, i});
    }
    dfs(1);
    for (int u:a)
    {
        if (inb[u])
        {
            while (b.back()!=u)
            {
                cout << b.back() << ' ';
                inb[b.back()]=0;
                b.pop_back();
            }
            cout << u << '\n';
        }
        else
        {
            inb[u]=1;
            b.push_back(u);
        }
    }
}

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