Submission #885047

#	Time	Username	Problem	Language	Result	Execution time	Memory
885047		codefox	Senior Postmen (BOI14_postmen)	C++14	0 / 100	0 ms	348 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

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

void dfs(int i)
{
    cout << i << " " << graph[i].size() << endl;
    while (graph[i].size())
    {
        cout << i << " ";
        pii ele = graph[i][0];
        graph[i][0] = graph[i].back();
        graph[graph[i][0].first][graph[i][0].second].second = 0;
        graph[i].pop_back();

        cout << i << " ";
        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();

        cout << i << endl;
        dfs(r1);
    }

    s.push(i);
    if (ins[i])
    {
        vector<int> v;
        do
        {
            ins[s.top()] = false;
            v.push_back(s.top());
            s.pop();
        }
        while (s.size() && s.top() != i);
        conn.push_back(v);
    }
    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);

    for (vector<int> ele:conn)
    {
        for (int ele2:ele) cout << ele2+1 << " ";
        cout << endl;
    }
    return 0;
}

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