Submission #223687

#	Time	Username	Problem	Language	Result	Execution time	Memory
223687		DystoriaX	Rigged Roads (NOI19_riggedroads)	C++14	10 / 100	163 ms	17784 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, idx;
};

int N, E;
vector<Edge> edge;
vector<int> R, W;
bitset<300010> on;
int toCheck;
DSU s;

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;
        edge[i].idx = i;
    }

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

    sort(R.begin(), R.end());

    for(auto &k : R) on[k] = true;

    for(int i = 0; i < E; i++) if(!on[i]) toCheck = i;

    int wg = 1;
    for(auto &k : R){
        if(toCheck < k){
            if(s.same(edge[toCheck].u, edge[toCheck].v)) W[toCheck] = wg++;
        }

        s.join(edge[k].u, edge[k].v);
        W[k] = wg++;
    }

    if(!W[toCheck]) W[toCheck] = E;

    for(int i = 0; i < E; i++) cout << W[i] << " \n"[i == E - 1];
        // cout << "\n";

    return 0;
}

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