Submission #643189

#	Time	Username	Problem	Language	Result	Execution time	Memory
643189		FedShat	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	266 ms	35736 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

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

vector<vector<pair<int, int>>> g;
vector<pair<int, int>> par;
vector<int> tin, tout;

void dfs(int v, int p) {
    static int T = 0;
    tin[v] = T++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = {v, i};
            dfs(u, v);
        }
    }
    tout[v] = T;
}

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

struct DSU {
    vector<int> p;

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

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

    void unite(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        p[v] = u;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        e[i] = {u, v};
    }
    vector<bool> tr(m);
    g.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int x;
        cin >> x;
        --x;
        tr[x] = 1;
        auto [u, v] = e[x];
        g[u].push_back({v, x});
        g[v].push_back({u, x});
    }
    par.resize(n, {-1, -1});
    tin.resize(n);
    tout.resize(n);
    dfs(0, -1);
    int ind = 1;
    vector<int> ans(m, -1);
    DSU t(n);
    for (int i = 0; i < m; ++i) {
        auto [u, v] = e[i];
        if (tr[i]) {
            if (ans[i] == -1) {
                if (!is_anc(u, v)) {
                    swap(u, v);
                }
                t.unite(u, v);
                ans[i] = ind++;
            }
            continue;
        }
        vector<int> cur;
        while (!is_anc(u, v)) {
            // if (ans[par[u].second] == -1) {
            //     cur.push_back(par[u].second);
            // }
            // u = par[u].first;
            int head = t.get(u);
            if (is_anc(head, v)) {
                break;
            }
            cur.push_back(par[head].second);
            t.unite(par[head].first, head);
            u = par[head].first;
        }
        while (!is_anc(v, u)) {
            // if (ans[par[v].second] == -1) {
            //     cur.push_back(par[v].second);
            // }
            // v = par[v].first;
            int head = t.get(v);
            if (is_anc(head, u)) {
                break;
            }
            cur.push_back(par[head].second);
            t.unite(par[head].first, head);
            v = par[head].first;
        }
        sort(cur.begin(), cur.end());
        for (int j : cur) {
            assert(ans[j] == -1);
            ans[j] = ind++;
        }
        assert(ans[i] == -1);
        ans[i] = ind++;
    }
    for (int i : ans) {
        cout << 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