Submission #492641

#	Time	Username	Problem	Language	Result	Execution time	Memory
492641		Rainbowbunny	Senior Postmen (BOI14_postmen)	C++17	55 / 100	640 ms	139976 KiB

postmen

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

const int MAXN = 5e5 + 5;

int n, m;
set <int> Adj[MAXN];
vector <int> Ans[MAXN];
bool In[MAXN];

void Find(int node, int id)
{
    if(Adj[node].empty())
    {
        Ans[id].push_back(node);
        return;
    }
    int tmp = *Adj[node].begin();
    Adj[node].erase(Adj[node].begin());
    Adj[tmp].erase(node);
    Find(tmp, id);
    Ans[id].push_back(node);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].insert(v);
        Adj[v].insert(u);
    }
    for(int i = 1; i <= n; i++)
    {
        if((int)Adj[i].size())
        {
            Find(i, i);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        stack <int> S;
        for(auto x : Ans[i])
        {
            if(In[x])
            {
                cout << x << ' ';
                while(S.top() != x)
                {
                    cout << S.top() << ' ';
                    In[S.top()] = false;
                    S.pop();
                }
                cout << '\n';
            }
            else
            {
                S.push(x);
                In[x] = true;
            }
        }
    }
}

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