oj.uz

Submission #413566

# Submission time Handle Problem Language Result Execution time Memory
413566 2021-05-28T23:04:03 Z shivensinha4 Rigged Roads (NOI19_riggedroads) C++17
0 / 100
 975 ms 262148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 836 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 836 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 850 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 975 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 836 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -