Submission #1119597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119597		vjudge1	Senior Postmen (BOI14_postmen)	C++17	100 / 100	481 ms	51132 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7;

bool vis[mxN], dd[mxN];
int n, m;
vector<ii> w[mxN];

void Euler_Cycle(int cur)
{
    vector<int> v;
    while (1)
    {
        if (vis[cur])
        {
            while (1)
            {
                int j = v.back();
                v.pop_back();
                vis[j] = 0;

                cout << j << " ";

                if (j == cur)
                    break;
            }
            cout << '\n';
        }
        v.push_back(cur);
        vis[cur] = 1;

        while (w[cur].size() && dd[w[cur].back().se])
            w[cur].pop_back();
        if (w[cur].empty())
            return;

        dd[w[cur].back().se] = 1;
        cur = w[cur].back().fi;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back({v, i});
        w[v].push_back({u, i});
    }

    for (int i = 1; i <= n; i++)
        Euler_Cycle(i);
}

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