oj.uz

Submission #456293

# Submission time Handle Problem Language Result Execution time Memory
456293 2021-08-06T11:06:20 Z arujbansal Rigged Roads (NOI19_riggedroads) C++17
10 / 100
 367 ms 64804 KB 
#include <bits/stdc++.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 3e5 + 5, INF = 1e9 + 5, MXK = 21;
int N, E, timer, available_weight;
vector<pair<int, int>> edges;
vector<pair<int, int>> adj_keep[MXN];
bool keep[MXN];
int tin[MXN], tout[MXN], binlift_par[MXN][MXK], ufds_info[MXN], edge_idx[MXN], ans[MXN];

void dfs(int u, int p) {
    tin[u] = timer++;

    for (int j = 1; j < MXK; j++)
        binlift_par[u][j] = binlift_par[binlift_par[u][j - 1]][j - 1];

    for (const auto &[v, idx] : adj_keep[u]) {
        if (v == p) continue;

        binlift_par[v][0] = u;

        edge_idx[v] = idx;
        dfs(v, u);
    }

    tout[u] = timer - 1;
}

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

int query_lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;

    for (int j = MXK - 1; j >= 0; j--) {
        int lift = binlift_par[u][j];
        if (is_anc(lift, v)) continue;

        u = lift;
    }

    return binlift_par[u][0];
}

int ufds_par(int x) {
    if (ufds_info[x] < 0) return x;
    return ufds_info[x] = ufds_par(ufds_info[x]);
}

void unite(int u, int v) {
    u = ufds_par(u), v = ufds_par(v);
    if (u == v) return;

    ufds_info[u] += ufds_info[v];
    ufds_info[v] = u;
}

void fill_path(int u, int v) {
    int lca = query_lca(u, v);
    u = ufds_par(u), v = ufds_par(v);

    vector<int> path_edges;

    while (u != lca && is_anc(lca, u)) {
        path_edges.push_back(edge_idx[u]);
        
        unite(binlift_par[u][0], u);
        u = ufds_par(u);
    }

    while (v != lca && is_anc(lca, v)) {
        path_edges.push_back(edge_idx[v]);
        
        unite(binlift_par[v][0], v);
        v = ufds_par(v);
    }

    sort(all(path_edges));

    for (const auto &idx : path_edges)
        ans[idx] = available_weight++;
}

void solve() {
    cin >> N >> E;

    edges.resize(E);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
        u--, v--;
    }

    for (int i = 0; i < N - 1; i++) {
        int idx;
        cin >> idx;
        idx--;

        keep[idx] = true;

        adj_keep[edges[idx].first].emplace_back(edges[idx].second, idx);
        adj_keep[edges[idx].second].emplace_back(edges[idx].first, idx);
    }

    dfs(0, -1);

    for (int i = 0; i <= N; i++)
        ufds_info[i] = -1;

    available_weight = 1;

    for (int i = 0; i < E; i++) {
        if (keep[i]) continue;

        fill_path(edges[i].first, edges[i].second);
        ans[i] = available_weight++;
    }

    for (int i = 0; i < E; i++) {
        if (ans[i] == 0)
            ans[i] = available_weight++;

        cout << ans[i] << " ";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 32508 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 290 ms 54808 KB Output is correct
2 Correct 311 ms 61468 KB Output is correct
3 Correct 71 ms 23200 KB Output is correct
4 Correct 121 ms 31212 KB Output is correct
5 Correct 367 ms 64804 KB Output is correct

Subtask #6
0 / 12.0

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

Subtask #7
0 / 32.0

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