Submission #914808

#	Time	Username	Problem	Language	Result	Execution time	Memory
914808		f0rizen	Rigged Roads (NOI19_riggedroads)	C++17	58 / 100	2031 ms	40512 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;
};

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