Submission #223706

#	Time	Username	Problem	Language	Result	Execution time	Memory
223706		DystoriaX	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	371 ms	49644 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

class DSU{
private:
    vector<int> p;

public:
    void init(int sz){
        p.resize(sz + 1);
        iota(p.begin(), p.end(), 0);
    }

    int findR(int x){
        return p[x] == x ? x : p[x] = findR(p[x]);
    }

    bool same(int a, int b){
        return findR(a) == findR(b);
    }

    void join(int a, int b){
        p[findR(a)] = findR(b);
    }
};

struct Edge{
    int u, v;
};

int N, E;
vector<Edge> edge;
vector<int> R, W;
bitset<300010> on;
DSU s;
int par[300010], d[300010], idx[300010];
vector<pair<int, int> > adj[300010];
set<int> q;

void dfs(int u, int p){
    for(auto &k : adj[u]){
        int v, id;

        tie(v, id) = k;

        if(v == p) continue;

        d[v] = d[u] + 1;
        par[v] = u, idx[v] = id;

        dfs(v, u);
    }
}

void query(int a, int b){
    while(a != b){
        if(d[a] < d[b]) swap(a, b);

        while(d[a] > d[b]){
            if(!s.same(a, par[a])){
                s.join(a, par[a]);
                q.insert(idx[a]);
                a = par[a];
            } else a = s.findR(a);
        }

        if(d[a] == d[b] && a != b){
            if(!s.same(a, par[a])){
                s.join(a, par[a]);
                q.insert(idx[a]);
                a = par[a];
            } else a = s.findR(a);

            swap(a, b);

            if(!s.same(a, par[a])){
                s.join(a, par[a]);
                q.insert(idx[a]);
                a = par[a];
            } else a = s.findR(a);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> E;

    edge.resize(E); W.assign(E, 0); s.init(N);

    for(int i = 0; i < E; i++){
        cin >> edge[i].u >> edge[i].v;
    }

    R.resize(N - 1);
    for(int i = 0; i < N - 1; i++){
        cin >> R[i], --R[i];

        on[R[i]] = true;

        adj[edge[R[i]].u].emplace_back(edge[R[i]].v, R[i]);
        adj[edge[R[i]].v].emplace_back(edge[R[i]].u, R[i]);
    }

    dfs(1, 1);

    int wg = 1;
    for(int i = 0; i < E; i++){
        if(!W[i]){
            if(on[i]){
                if(d[edge[i].u] < d[edge[i].v]) swap(edge[i].u, edge[i].v);

                s.join(edge[i].u, edge[i].v);
                W[i] = wg++;
            } else {
                query(edge[i].u, edge[i].v);
                for(auto &k : q){
                    W[k] = wg++;
                }

                q.clear();

                W[i] = wg++;
            }
        }
        cout << W[i] << " \n"[i == E - 1];
    }

    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