oj.uz

Submission #914830

# Submission time Handle Problem Language Result Execution time Memory
914830 2024-01-22T17:53:54 Z f0rizen Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 245 ms 40492 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, ind;
};

struct DSU {
    vector<int> p;

    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int root(int v) {
        if (p[v] == v) {
            return v;
        }
        return p[v] = root(p[v]);
    }

    bool unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) {
            return false;
        }
        p[v] = u;
        return true;
    }
};

vector<vector<Edge>> g;
vector<int> par, up;
vector<int> tin, tout;
int timer;

void dfs(int v, int p = -1) {
    tin[v] = timer++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = v;
            up[u] = i;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}

bool is_anc(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edg(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[i] = {u, v};
    }
    g.resize(n);
    vector<bool> mst(m);
    for (int i = 1; i < n; ++i) {
        int e;
        cin >> e;
        --e;
        auto [u, v] = edg[e];
        g[u].push_back({v, e});
        g[v].push_back({u, e});
        mst[e] = 1;
    }
    par.resize(n);
    up.resize(n);
    tin.resize(n);
    tout.resize(n);
    dfs(0);
    DSU d(n);
    int cl = 0;
    vector<int> ans(m, -1);
    for (int i = 0; i < m; ++i) {
        if (ans[i] != -1) {
            continue;
        }
        auto [u, v] = edg[i];
        if (mst[i]) {
            if (!is_anc(u, v)) {
                swap(u, v);
            }
            d.unite(u, v);
            ans[i] = cl++;
            continue;
        }
        vector<int> cur;
        while (!is_anc(u, v)) {
            int leader = d.root(u);
            if (is_anc(leader, v)) {
                break;
            }
            cur.push_back(up[leader]);
            d.unite(par[leader], leader);
            u = par[leader];
        }
        while (!is_anc(v, u)) {
            int leader = d.root(v);
            if (is_anc(leader, u)) {
                break;
            }
            cur.push_back(up[leader]);
            d.unite(par[leader], leader);
            v = par[leader];
        }
        sort(cur.begin(), cur.end());
        for (auto j : cur) {
            ans[j] = cl++;
        }
        ans[i] = cl++;
    }
    for (auto i : ans) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11972 KB Output is correct
2 Correct 57 ms 16540 KB Output is correct
3 Correct 60 ms 9872 KB Output is correct
4 Correct 92 ms 31928 KB Output is correct
5 Correct 107 ms 32956 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18180 KB Output is correct
2 Correct 35 ms 8532 KB Output is correct
3 Correct 19 ms 4444 KB Output is correct
4 Correct 42 ms 13616 KB Output is correct
5 Correct 16 ms 5724 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 33184 KB Output is correct
2 Correct 245 ms 38308 KB Output is correct
3 Correct 30 ms 11244 KB Output is correct
4 Correct 71 ms 16568 KB Output is correct
5 Correct 208 ms 40492 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23500 KB Output is correct
2 Correct 54 ms 16468 KB Output is correct
3 Correct 229 ms 36180 KB Output is correct
4 Correct 233 ms 33660 KB Output is correct
5 Correct 12 ms 3420 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 33 ms 11972 KB Output is correct
10 Correct 57 ms 16540 KB Output is correct
11 Correct 60 ms 9872 KB Output is correct
12 Correct 92 ms 31928 KB Output is correct
13 Correct 107 ms 32956 KB Output is correct
14 Correct 58 ms 18180 KB Output is correct
15 Correct 35 ms 8532 KB Output is correct
16 Correct 19 ms 4444 KB Output is correct
17 Correct 42 ms 13616 KB Output is correct
18 Correct 16 ms 5724 KB Output is correct
19 Correct 161 ms 33184 KB Output is correct
20 Correct 245 ms 38308 KB Output is correct
21 Correct 30 ms 11244 KB Output is correct
22 Correct 71 ms 16568 KB Output is correct
23 Correct 208 ms 40492 KB Output is correct
24 Correct 99 ms 23500 KB Output is correct
25 Correct 54 ms 16468 KB Output is correct
26 Correct 229 ms 36180 KB Output is correct
27 Correct 233 ms 33660 KB Output is correct
28 Correct 12 ms 3420 KB Output is correct
29 Correct 204 ms 34224 KB Output is correct
30 Correct 233 ms 35256 KB Output is correct
31 Correct 210 ms 33920 KB Output is correct
32 Correct 57 ms 9988 KB Output is correct
33 Correct 205 ms 34188 KB Output is correct