Submission #492645

#	Time	Username	Problem	Language	Result	Execution time	Memory
492645		Rainbowbunny	Senior Postmen (BOI14_postmen)	C++17	100 / 100	447 ms	109104 KiB

postmen

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

const int MAXN = 5e5 + 5;

int n, m;
int ii[MAXN];
vector <pair <int, int> > Adj[MAXN];
vector <int> Ans[MAXN];
bool In[MAXN], Used[MAXN];

void Find(int node, int id)
{
    while(ii[node] < (int)Adj[node].size() and Used[Adj[node][ii[node]].second])
    {
        ii[node]++;
    }
    if(ii[node] < (int)Adj[node].size())
    {
        Used[Adj[node][ii[node]].second] = true;
        Find(Adj[node][ii[node]].first, id);
    }
    if(In[node])
    {
        cout << node << ' ';
        while(Ans[id].back() != node)
        {
            cout << Ans[id].back() << ' ';
            In[Ans[id].back()] = false;
            Ans[id].pop_back();
        }
        cout << '\n';
    }
    else
    {
        In[node] = true;
        Ans[id].push_back(node);
    }
}

int main()
{
    // freopen("test_input.txt", "r", stdin);
    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].emplace_back(v, i);
        Adj[v].emplace_back(u, i);
    }
    for(int i = 1; i <= n; i++)
    {
        if((int)Adj[i].size())
        {
            Find(i, i);
        }
    }
}

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