oj.uz

Submission #643186

# Submission time Handle Problem Language Result Execution time Memory
643186 2022-09-21T12:31:28 Z FedShat Rigged Roads (NOI19_riggedroads) C++17
19 / 100
 285 ms 35720 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

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

vector<vector<pair<int, int>>> g;
vector<pair<int, int>> par;
vector<int> tin, tout;

void dfs(int v, int p) {
    static int T = 0;
    tin[v] = T++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            par[u] = {v, i};
            dfs(u, v);
        }
    }
    tout[v] = T;
}

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

struct DSU {
    vector<int> p;

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

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

    void unite(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        p[v] = u;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        e[i] = {u, v};
    }
    vector<bool> tr(m);
    g.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int x;
        cin >> x;
        --x;
        tr[x] = 1;
        auto [u, v] = e[x];
        g[u].push_back({v, x});
        g[v].push_back({u, x});
    }
    par.resize(n, {-1, -1});
    tin.resize(n);
    tout.resize(n);
    dfs(0, -1);
    int ind = 1;
    vector<int> ans(m, -1);
    DSU t(n);
    for (int i = 0; i < m; ++i) {
        auto [u, v] = e[i];
        if (tr[i]) {
            if (ans[i] == -1) {
                if (!is_anc(u, v)) {
                    swap(u, v);
                }
                t.unite(u, v);
                ans[i] = ind++;
            }
            continue;
        }
        vector<int> cur;
        while (!is_anc(u, v)) {
            // if (ans[par[u].second] == -1) {
            //     cur.push_back(par[u].second);
            // }
            // u = par[u].first;
            int head = t.p[u];
            if (is_anc(head, v)) {
                break;
            }
            cur.push_back(par[head].second);
            t.unite(par[head].first, head);
            u = par[head].first;
        }
        while (!is_anc(v, u)) {
            // if (ans[par[v].second] == -1) {
            //     cur.push_back(par[v].second);
            // }
            // v = par[v].first;
            int head = t.p[v];
            if (is_anc(head, u)) {
                break;
            }
            cur.push_back(par[head].second);
            t.unite(par[head].first, head);
            v = par[head].first;
        }
        sort(cur.begin(), cur.end());
        for (int j : cur) {
            // assert(ans[j] == -1);
            ans[j] = ind++;
        }
        // assert(ans[i] == -1);
        ans[i] = ind++;
    }
    for (int i : ans) {
        cout << i << " ";
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10104 KB Output is correct
2 Correct 72 ms 14264 KB Output is correct
3 Correct 76 ms 6932 KB Output is correct
4 Correct 128 ms 27612 KB Output is correct
5 Correct 127 ms 28980 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 15704 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 179 ms 29384 KB Output is correct
2 Correct 258 ms 34028 KB Output is correct
3 Correct 40 ms 9892 KB Output is correct
4 Correct 65 ms 14684 KB Output is correct
5 Correct 282 ms 35720 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 20820 KB Output is correct
2 Correct 85 ms 14692 KB Output is correct
3 Incorrect 285 ms 32020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -