Submission #413618

#	Time	Username	Problem	Language	Result	Execution time	Memory
413618		shivensinha4	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	357 ms	52220 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

class UFDS {
public:
    vi p, rank;
    vector<ii> mn; int count = 0;

    UFDS(int n, vi depth) {
        p.resize(n); rank.resize(n); mn.resize(n);
        for_(i, 0, n) {
            p[i] = i;
            mn[i] = {depth[i], i};
        }
        count = n;
    }
    int getParent(int i) {
        return (p[i] == i) ? i : (p[i] = getParent(p[i]));
    }
    void join(int i, int j) {
        int a = getParent(i), b = getParent(j);
        if (a == b) return;
        count -= 1;
        mn[a] = mn[b] = min(mn[a], mn[b]);

        if (rank[a] > rank[b]) {
            p[b] = a;
        } else {
            p[a] = b;
            if (rank[a] == rank[b]) rank[b] += 1;
        }
    }
};



int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<vector<ii>> adj(n);
    vector<ii> edges;
    vector<bool> used(m);

    for_(i, 0, m) {
        int a, b; cin >> a >> b;
        edges.push_back({a-1, b-1});
    }

    for_(i, 0, n-1) {
        int k; cin >> k;
        k -= 1;
        used[k] = true;
        adj[edges[k][0]].push_back({edges[k][1], k});
        adj[edges[k][1]].push_back({edges[k][0], k});
    }

    vi par(n, -1), pedge(n, -1), depth(n);
    function<void(int)> dfs = [&] (int p) {
        for (auto &i: adj[p]) if (i[0] != par[p]) {
            par[i[0]] = p;
            pedge[i[0]] = i[1];
            depth[i[0]] = depth[p]+1;
            dfs(i[0]);
        }
    };

    dfs(0);
    vi val(m, -1);
    int pt = 1;

    UFDS ufds(n, depth);

    for_(i, 0, m) {
        if (!used[i]) {
//            cout << "huh edge " << i << " was not used " << endl;
            int a = ufds.mn[ufds.getParent(edges[i][0])][1], b = ufds.mn[ufds.getParent(edges[i][1])][1];
            vi curr;
            while (a != b) {
                assert(a == ufds.mn[ufds.getParent(a)][1] and b == ufds.mn[ufds.getParent(b)][1]);
                if (depth[a] < depth[b]) swap(a, b);
                ufds.join(a, par[a]);
//                cout << "hence removing edge " << pedge[a] << endl;
                curr.push_back(pedge[a]);
                a = ufds.mn[ufds.getParent(par[a])][1];
            }

            sort(curr.begin(), curr.end());
            for (auto j: curr) if (val[j] == -1) val[j] = pt++;
            val[i] = pt++;
        } else if (val[i] == -1) val[i] = pt++;
    }

    for (auto i: val) cout << i << " ";
    cout << endl;
}

• 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