oj.uz

Submission #223687

# Submission time Handle Problem Language Result Execution time Memory
223687 2020-04-16T04:15:14 Z DystoriaX Rigged Roads (NOI19_riggedroads) C++14
10 / 100
 163 ms 17784 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 6648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 13816 KB Output is correct
2 Correct 151 ms 14200 KB Output is correct
3 Correct 42 ms 4092 KB Output is correct
4 Correct 65 ms 6904 KB Output is correct
5 Correct 163 ms 17784 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -