Submission #413566

#	Time	Username	Problem	Language	Result	Execution time	Memory
413566		shivensinha4	Rigged Roads (NOI19_riggedroads)	C++17	0 / 100	975 ms	262148 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, mn; int count = 0;

    UFDS(int n) {
        p.resize(n); rank.resize(n); mn.resize(n);
        for_(i, 0, n) p[i] = mn[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;
//        take.push_back(k);
        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);

    for_(i, 0, m) if (!used[i]) {
        int a = ufds.getParent(edges[i][0]), b = ufds.getParent(edges[i][1]);
//        cout << "joining " << a << " " << b << endl;
        vi curr;
        while (a != b) {
            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])];
        }

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

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32