Submission #1127099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127099		bruh	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	494 ms	83412 KiB

riggedroads

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>

using namespace std;
const int maxn = 3e5 + 5;
int n, m;
int head[maxn], id[maxn], ind[maxn], sz[maxn], par[maxn], h[maxn], ans[maxn], mark[maxn], who[maxn], chosen[maxn];
vector<ii> adj[maxn];
array<int, 2> edges[maxn];
vector<int> order;

struct DS{
    int seg[4 * maxn];
    void upd(int pos, int val, int id = 1, int l = 1, int r = m)
    {
        if (l == r) return seg[id] = val, void();
        int mid = (l + r) / 2;
        if (pos <= mid) upd(pos, val, id * 2, l, mid);
        else upd(pos, val, id * 2 + 1, mid + 1, r);
        seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
    int qry(int lx, int rx, int id = 1, int l = 1, int r = m)
    {
        if (lx > r || l > rx || lx > rx) return 0;
        if (lx <= l && r <= rx) return seg[id];
        int mid = (l + r) / 2;
        return qry(lx, rx, id * 2, l, mid) + qry(lx, rx, id * 2 + 1, mid + 1, r);
    }
    int walk(int k = 1, int id = 1, int l = 1, int r = m)
    {
        if (l == r) return l;
        int mid = (l + r) / 2;
        int nothing = mid - l + 1 - seg[id * 2];
        if (nothing >= k) return walk(k, id * 2, l, mid);
        return walk(k - nothing, id * 2 + 1, mid + 1, r);
    }
    int get(int lx, int rx, int id = 1, int l = 1, int r = m)
    {
        if (l > rx || lx > r) return -1;
        if (l == r) return l;
        int mid = (l + r) / 2;
        int ans = -1;
        if (seg[id * 2] != mid - l + 1) ans = get(lx, rx, id * 2, l, mid);
        if (ans != -1) return ans;
        if (seg[id * 2 + 1] != r - mid) return get(lx, rx, id * 2 + 1, mid + 1, r);
        return -1;
    }
} IND, HLD;

void dfs(int x = 1, int p = 0)
{
    sz[x] = 1;
    for (auto i : adj[x]) if (i.first != p)
        dfs(i.first, x),
        sz[x] += sz[i.first];
}

void hld(pair<int,int> pa = {1, 0}, int p = 0, int top = 1)
{
    static int cnt = 0;
    int x = pa.first;
    head[x] = top;
    par[x] = p;
    h[x] = h[p] + 1;
    id[x] = ++cnt;
    who[cnt] = x;
    ind[cnt] = pa.second;
    ii fat = {-1, -1};
    for (auto i : adj[x]) if (i.first != p)
        fat = max(fat, make_pair(sz[i.first], i.first));
    if (fat.second != -1)
        for (auto i : adj[x]) if (i.first != p && i.first == fat.second)
            hld(i, x, top);
    for (auto i : adj[x]) if (i.first != p && i.first != fat.second)
        hld(i, x, i.first);
}

int qry(int u, int v)
{
    vector<int> path;
    while (head[u] != head[v])
    {
        if (h[head[u]] > h[head[v]]) swap(u, v);
        while (true)
        {
            int x = HLD.get(id[head[v]], id[v]);
            if (x == -1) break;
            path.emplace_back(who[x]);
            int rem = IND.walk();
            IND.upd(rem, 1);
            HLD.upd(x, 1);
        }
        v = par[head[v]];
    }
    if (id[u] > id[v]) swap(u, v);
    while (true)
    {
        int x = HLD.get(id[u] + 1, id[v]);
        if (x == -1) break;
        path.emplace_back(who[x]);
        int rem = IND.walk();
        IND.upd(rem, 1);
        HLD.upd(x, 1);
    }
    sort(path.begin(), path.end(), [](int x, int y){
            x = id[x];
            y = id[y];
            return ind[x] < ind[y];
         });
    for (int i : path)
        order.emplace_back(i);
    return path.size();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> edges[i][0] >> edges[i][1];
    for (int j = 1, i; j < n; j++)
        cin >> i,
        chosen[i] = 1,
        adj[edges[i][0]].emplace_back(edges[i][1], i),
        adj[edges[i][1]].emplace_back(edges[i][0], i);
    dfs();
    hld();
    for (int i = 1; i <= m; i++)
    {
        int u = edges[i][0], v = edges[i][1];
        if (h[u] > h[v]) swap(u, v);
        if (chosen[i])
        {
            if (!HLD.qry(id[v], id[v]))
            {
                ans[i] = IND.walk();
                IND.upd(ans[i], 1);
                mark[ans[i]] = 1;
                HLD.upd(id[v], 1);
            }
            continue;
        }
        int blank = qry(edges[i][0], edges[i][1]);
        ans[i] = IND.walk();
        IND.upd(ans[i], 1);
        mark[ans[i]] = 1;
    }
    int cur = 1;
    for (int i : order)
    {
        i = ind[id[i]];
        if (ans[i]) continue;
        while (mark[cur]) cur++;
        ans[i] = cur;
        mark[cur] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        if (ans[i]) continue;
        while (mark[cur]) cur++;
        ans[i] = cur;
        mark[cur] = 1;
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << " ";
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32