Submission #1126993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126993		khoad	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	418 ms	74872 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf32 ((int)1e9 + 7)
#define inf64 ((long long)1e18 + 7)
#define MASK32(x) (1 << (x))
#define MASK64(x) (1ll << (x))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define all(a) begin(a), end(a)
#define isz(a) ((int)a.size())

const int N = 3e5 + 1, LG = 19;

int n, m;
pair<int, int> e[N];
vector<int> g[N], mst[N];
int par[LG][N], par1[N], par_id[N], dep[N];
bool is_mst[N];
int res[N];

void dfs(int u) {
    par1[u] = u;
    for(int i : mst[u]) {
        int v = u ^ e[i].first ^ e[i].second;
        if(v == par[0][u]) continue;
        par[0][v] = u;
        par_id[v] = i;
        dep[v] = dep[u] + 1;
        for(int k = 1; k < LG; ++k) par[k][v] = par[k - 1][par[k - 1][v]];
        dfs(v);
    }
}

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 0; i < LG; ++i)
        if(BIT(dep[u] - dep[v], i)) u = par[i][u];
    if(u == v) return u;
    for(int i = LG - 1; i >= 0; --i)
        if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
    return par[0][u];
}

int find(int u) {
    return (par1[u] == u) ? u : (par1[u] = find(par1[u]));
}

void full() {
    dfs(1);
    int cur = 0;
    for(int i = 1; i <= m; ++i) {
        if(is_mst[i]) {
            if(!res[i]) res[i] = ++cur;
            continue;
        }
        auto [u, v] = e[i];
        int l = lca(u, v);
        vector<int> path;
        while(dep[u] > dep[l]) {
            int p = find(u);
            if(p == u) {
                path.push_back(par_id[u]);
                par1[u] = l;
                u = par[0][u];
            }
            else u = p;
        }
        while(dep[v] > dep[l]) {
            int p = find(v);
            if(p == v) {
                path.push_back(par_id[v]);
                par1[v] = l;
                v = par[0][v];
            }
            else v = p;
        }
        sort(all(path));
        for(int id : path)
            if(!res[id]) res[id] = ++cur;
        res[i] = ++cur;
    }
    for(int i = 1; i <= m; ++i) cout << res[i] << ' ';
}

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

    // freopen("PALACE.inp", "r", stdin);
    // freopen("PALACE.out", "w", stdout);

    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> e[i].first >> e[i].second;
        g[e[i].first].push_back(i);
        g[e[i].second].push_back(i);
    }
    for(int i = 1, id; i < n; ++i) {
        cin >> id;
        is_mst[id] = 1;
        mst[e[id].first].push_back(id);
        mst[e[id].second].push_back(id);
    }
    full();

    return 0;
}

• 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