Submission #917489

#	Time	Username	Problem	Language	Result	Execution time	Memory
917489		406	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	285 ms	65028 KiB

riggedroads

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 3e5 + 5;

namespace dsu {
        int dpr[N];
        int gpr(int x) {
                return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]);
        }
        void merge(int u, int v) {
                dpr[gpr(u)] = gpr(v);
        }
}

int st[N], fn[N], T, pr[N], up[N], mn[N], W[N], n, m;
ar E[N];
bool ok[N];
vector<int> ad[N];
vector<ar> adj[N];

bool is_p(int p, int v) {
        return st[p] <= st[v] && fn[v] <= fn[p];
}

void dfs(int v) {
        st[v] = T++;
        for (auto [u, id]: adj[v]) if (u != pr[v]) {
                up[u] = id;
                pr[u] = v;
                dfs(u);
        }
        fn[v] = T;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        FOR(i, 0, m) {
                cin >> E[i][0] >> E[i][1];
                --E[i][0], --E[i][1];
        }
        FOR(i, 1, n) {
                int x; cin >> x; --x;
                auto [u, v] = E[x];
                adj[v].push_back({u, x});
                adj[u].push_back({v, x});
                ok[x] = true;
        }
        fill(mn, mn + m, m);
        iota(dsu::dpr, dsu::dpr + n, 0);
        
        up[0] = -1;
        dfs(0);
        FOR(i, 0, m) if (!ok[i]) {
               auto [u, v] = E[i];
               int tu = dsu::gpr(u), tv = dsu::gpr(v);
               while (!is_p(tu, v)) {
                       assert(up[tu] != -1);
                       mn[up[tu]] = i;
                       dsu::merge(tu, pr[tu]);
                       tu = dsu::gpr(tu); 
               }
               while (!is_p(tv, u)) {
                       assert(up[tv] != -1);
                        mn[up[tv]] = i;
                        dsu::merge(tv, pr[tv]);
                        tv = dsu::gpr(tv);
               }
        }
        for (int i = m - 1; i >= 0; --i) if (ok[i]) 
                ad[mn[i]].push_back(i);

        int r = m;
        for (int i = m - 1; i >= 0; --i) {
               if (!ok[i]) {
                       W[i] = r--;
                       for (auto t: ad[i]) if (t > i) 
                               W[t] = r--;
               }
               else if (mn[i] > i)
                       W[i] = r--; 
        }
        FOR(i, 0, m) 
                cout << W[i] << ' ';
        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