제출 #1262383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262383		damjandavkov	Senior Postmen (BOI14_postmen)	C++20	0 / 100	24 ms	3776 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, 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 = 0;
    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;
            if (k < m - 1 && d[u] == 1)
                continue;
            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]--;
            t = u;
            o.push_back(t);
            break;
        }
    }
    o.push_back(0);
    vector<bool> w(n, 0);
    vector<int> pr(m + 1);
    for (i = 0; i <= m; i++)
        pr[i] = i - 1;
    for (i = 0; i <= m; i++)
    {
        if (w[o[i]])
        {
            cout << o[i] + 1;
            for (j = i - 1; j >= 0 && o[j] != o[i]; j = pr[j])
            {
                w[o[j]] = 0;
                cout << ' ' << o[j] + 1;
            }
            pr[i] = pr[j];
            cout << '\n';
        }
        else
            w[o[i]] = 1;
    }
}

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