Submission #697914

#	Time	Username	Problem	Language	Result	Execution time	Memory
697914		mousebeaver	Senior Postmen (BOI14_postmen)	C++14	100 / 100	434 ms	80708 KiB

postmen

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pdi pair<double, int>
#define pcc pair<char, char>
#define tiii tuple<int, int, int>
#define tlii tuple<int, int, int>
#define tl tuple<ll, ll, ll, ll>
#define tls tuple<ll, ll, ll>
#define INF numeric_limits<ll>::max()/2
#define MOD 1000000007
#define MIO 1000000
#define mp make_pair
#include <bits/stdc++.h>
using namespace std;

/*void hierholzer(int i, vector<vector<pii>>& adjlist, vector<vector<bool>>& active, vector<int>& output)
{
    for(int k = 0; k < (int) adjlist[i].size(); k++)
    {
        if(active[i][k])
        {
            int j = adjlist[i][k].first;
            int ind = adjlist[i][k].second;
            active[i][k] = false;
            active[j][ind] = false;
            hierholzer(j, adjlist, active, output);
            output.push_back(j);
        }
    }
}*/

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

    int n, m;
    cin>>n>>m;
    vector<vector<pii>> adjlist(n, vector<pii> (0));
    vector<vector<bool>> active(n, vector<bool> (0));
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin>>a>>b;
        a--; b--;
        adjlist[a].push_back({b, adjlist[b].size()});
        adjlist[b].push_back({a, adjlist[a].size()-1});
    }
    for(int i = 0; i < n; i++)
    {
        active[i].assign(adjlist[i].size(), true);
    }

    vector<int> output(0);
    vector<int> ind(n, 0);
    stack<int> hierholzer;
    hierholzer.push(0);
    while(hierholzer.size())
    {
        int u = hierholzer.top();
        int index = ind[u];
        while(index < (int) adjlist[u].size() && !active[u][index])
        {
            index++;
        }
        ind[u] = index+1;
        if(index >= (int) adjlist[u].size())
        {
            hierholzer.pop();
            output.push_back(u);
        }
        else
        {
            hierholzer.push(adjlist[u][index].first);
            active[u][index] = false;
            active[adjlist[u][index].first][adjlist[u][index].second] = false;
        }
    }

    //output.push_back(0);
    //reverse(output.begin(), output.end());

    /*for(int i : output)
    {
        cout<<i+1<<" ";
    }
    cout<<"\n";*/

    stack<int> tour;
    vector<bool> instack(n, false);
    for(int i : output)
    {
        if(instack[i])
        {
            vector<int> senior(0);
            int v = -1;
            while(v != i)
            {
                v = tour.top();
                tour.pop();
                instack[v] = false;
                senior.push_back(v);
            }
            tour.push(i);
            instack[i] = true;
            for(int j : senior)
            {
                cout<<j+1<<" ";
            }
            cout<<"\n";
        }
        else
        {
            tour.push(i);
            instack[i] = true;
        }
    }

    return 0;
}

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