Submission #914830

#	Time	Username	Problem	Language	Result	Execution time	Memory
914830		f0rizen	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	245 ms	40492 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, ind;
};

struct DSU {
    vector<int> p;

    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int root(int v) {
        if (p[v] == v) {
            return v;
        }
        return p[v] = root(p[v]);
    }

    bool unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) {
            return false;
        }
        p[v] = u;
        return true;
    }
};

vector<vector<Edge>> g;
vector<int> par, up;
vector<int> tin, tout;
int timer;

void dfs(int v, int p = -1) {
    tin[v] = timer++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = v;
            up[u] = i;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}

bool is_anc(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edg(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[i] = {u, v};
    }
    g.resize(n);
    vector<bool> mst(m);
    for (int i = 1; i < n; ++i) {
        int e;
        cin >> e;
        --e;
        auto [u, v] = edg[e];
        g[u].push_back({v, e});
        g[v].push_back({u, e});
        mst[e] = 1;
    }
    par.resize(n);
    up.resize(n);
    tin.resize(n);
    tout.resize(n);
    dfs(0);
    DSU d(n);
    int cl = 0;
    vector<int> ans(m, -1);
    for (int i = 0; i < m; ++i) {
        if (ans[i] != -1) {
            continue;
        }
        auto [u, v] = edg[i];
        if (mst[i]) {
            if (!is_anc(u, v)) {
                swap(u, v);
            }
            d.unite(u, v);
            ans[i] = cl++;
            continue;
        }
        vector<int> cur;
        while (!is_anc(u, v)) {
            int leader = d.root(u);
            if (is_anc(leader, v)) {
                break;
            }
            cur.push_back(up[leader]);
            d.unite(par[leader], leader);
            u = par[leader];
        }
        while (!is_anc(v, u)) {
            int leader = d.root(v);
            if (is_anc(leader, u)) {
                break;
            }
            cur.push_back(up[leader]);
            d.unite(par[leader], leader);
            v = par[leader];
        }
        sort(cur.begin(), cur.end());
        for (auto j : cur) {
            ans[j] = cl++;
        }
        ans[i] = cl++;
    }
    for (auto i : ans) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    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