Submission #895567

#	Time	Username	Problem	Language	Result	Execution time	Memory
895567		codefox	Senior Postmen (BOI14_postmen)	C++14	100 / 100	330 ms	71248 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

vector<vector<pii>> graph;
stack<int> s;
vector<bool> ins;

void dfs(int i)
{
    while (graph[i].size())
    {
        pii ele = graph[i].back();
        graph[i].pop_back();

        int r1 = ele.first;
        int r2 = ele.second;
        graph[r1][r2] = graph[r1].back();
        graph[graph[r1][r2].first][graph[r1][r2].second].second = r2;
        graph[r1].pop_back();

        dfs(r1);
    }

    s.push(i);
    if (ins[i])
    {
        do
        {
            ins[s.top()] = false;
            cout << s.top()+1 << " ";
            s.pop();
        }
        while (s.size() && s.top() != i);
        cout << "\n";
    }
    ins[i] = true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    graph = vector<vector<pii>>(n);
    ins = vector<bool>(n, 0);
    for (int i =0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        int sa = graph[a].size();
        int sb = graph[b].size();
        graph[a].push_back({b, sb});
        graph[b].push_back({a, sa});
    }
    dfs(0);
    return 0;
}

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