Submission #527055

#	Time	Username	Problem	Language	Result	Execution time	Memory
527055		vishesh312	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	826 ms	94476 KiB

riggedroads

#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
const int mod = 1e9+7;
const int LOG = 20;

vector<pair<int, int>> edges;
vector<vector<int>> adj, lup;
vector<int> dist;

struct UnionFind {
    vector<int> link, siz, up;
    int n;
    UnionFind(int _n) {
        n = _n;
        siz.resize(n, 1);
        link.resize(n);
        iota(all(link), 0);
        up = link;
    }
    int find(int x) {
        if (x == link[x])
            return x;
        return link[x] = find(link[x]);
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (siz[a] < siz[b])
            swap(a, b);
        siz[a] += siz[b];
        link[b] = a;
        up[a] = (dist[up[a]] < dist[up[b]] ? up[a] : up[b]);
    }
};

void dfs(int u = 0, int p = -1) {
    for (int v: adj[u]) {
        if (v != p) {
            dist[v] = dist[u] + 1;
            lup[v][0] = u;
            for (int i = 1; i < LOG; ++i)
                lup[v][i] = lup[lup[v][i-1]][i-1];
            dfs(v, u);
        }
    }
}

int get_lca(int u, int v) {
    if (dist[u] > dist[v])
        swap(u, v);
    int dd = dist[v] - dist[u];
    for (int i = LOG - 1; i >= 0; --i)
        if (dd & (1 << i))
            v = lup[v][i];
    if (u == v)
        return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (lup[u][i] != lup[v][i]) {
            u = lup[u][i];
            v = lup[v][i];
        }
    }
    return lup[u][0];
}

void solve(int tc) {
    int n, m;
    cin >> n >> m;
    edges.resize(m); adj.resize(n); dist.resize(n); lup.resize(n, vector<int>(LOG));
    map<pair<int, int>, int> id;
    for (int i = 0; i < m; ++i) {
        auto &[u, v] = edges[i];
        cin >> u >> v;
        --u, --v;
        if (u > v)
            swap(u, v);
        id[make_pair(u, v)] = i;
    }
    vector<bool> is(m);
    for (int i = 0; i < n-1; ++i) {
        int x;
        cin >> x;
        auto [u, v] = edges[x-1];
        adj[u].push_back(v);
        adj[v].push_back(u);
        is[x-1] = true;
    }
    dfs();
    UnionFind uf(n);
    vector<int> we(m);
    int cur = 1;
    for (int i = 0; i < m; ++i) {
        auto [u, v] = edges[i];
        if (we[i])
            continue;
        if (is[i]) {
            we[i] = cur++;
            uf.unite(u, v);
            continue;
        }
        int l = get_lca(u, v);
        vector<int> vec;
        while (dist[uf.up[uf.find(u)]] > dist[l]) {
            int x = uf.up[uf.find(u)];
            vec.push_back(id[{min(x, lup[x][0]), max(x, lup[x][0])}]);
            uf.unite(u, lup[x][0]);
        }
        while (dist[uf.up[uf.find(v)]] > dist[l]) {
            int x = uf.up[uf.find(v)];
            vec.push_back(id[{min(x, lup[x][0]), max(x, lup[x][0])}]);
            uf.unite(v, lup[x][0]);
        }
        sort(all(vec));
        for (int x: vec)
            we[x] = cur++;
        we[i] = cur++;
    }
    for (int x: we)
        cout << x << " ";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    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