Submission #643176

#	Time	Username	Problem	Language	Result	Execution time	Memory
643176		FedShat	Rigged Roads (NOI19_riggedroads)	C++17	58 / 100	2062 ms	40400 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];
}

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);
    for (int i = 0; i < m; ++i) {
        if (tr[i]) {
            if (ans[i] == -1) {
                ans[i] = ind++;
            }
            continue;
        }
        auto [u, v] = e[i];
        vector<int> cur;
        while (!is_anc(u, v)) {
            if (ans[par[u].second] == -1) {
                cur.push_back(par[u].second);
            }
            u = par[u].first;
        }
        while (!is_anc(v, u)) {
            if (ans[par[v].second] == -1) {
                cur.push_back(par[v].second);
            }
            v = par[v].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: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32