Submission #1262404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262404		damjandavkov	Senior Postmen (BOI14_postmen)	C++20	100 / 100	333 ms	37304 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, i, j, k, t, f, u, hi, lo, md;
    cin >> n >> m;
    vector<int> p(n, 0), o = {0}, d(n);
    vector<vector<pair<int, bool> > > v(n);
    for (k = 0; k < m; k++)
    {
        cin >> i >> j;
        i--;
        j--;
        v[i].push_back({j, 0});
        v[j].push_back({i, 0});
    }
    for (k = 0; k < n; k++)
    {
        d[k] = v[k].size();
        sort(v[k].begin(), v[k].end());
    }
    t = f = 0;
    vector<bool> w(n, 0);
    w[0] = 1;
    for (k = 1; k <= m; k++)
    {
        for (; p[t] < v[t].size(); p[t]++)
        {
            if (v[t][p[t]].second)
                continue;
            u = v[t][p[t]].first;
            hi = v[u].size();
            lo = -1;
            while (hi - lo > 1)
            {
                md = (hi + lo) >> 1;
                if (v[u][md].first > t)
                    hi = md;
                else
                    lo = md;
            }
            v[u][lo].second = v[t][p[t]].second = 1;
            d[t]--;
            d[u]--;
            //cout << "C " << t << " " << u << " " << d[t] << " " << d[u] << " " << w[u] << endl;
            t = u;
            if (w[t])
            {
                //cout << "B " << t << endl;
                while (o.back() != t)
                {
                    w[o.back()] = 0;
                    cout << o.back() + 1 << " ";
                    o.pop_back();
                }
                cout << t + 1 << endl;
                if (o.size() == 1)
                {
                    o.pop_back();
                    w[t] = 0;
                    while (f < n && (!d[f] || w[f]))
                        f++;
                    if (f == n)
                        break;
                    t = f;
                    o.push_back(t);
                    w[t] = 1;
                    //cout << "A " << t << endl;
                }
            }
            else
            {
                //cout << "D " << t << endl;
                w[t] = 1;
                o.push_back(t);
            }
            break;
        }
    }

}

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