oj.uz

Submission #456326

# Submission time Handle Problem Language Result Execution time Memory
456326 2021-08-06T12:32:23 Z arujbansal Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 510 ms 62908 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

struct UFDS {
    int n;
    vector<int> info;
 
    UFDS() {}
 
    UFDS(int _n) { init(_n); }
 
    void init(int _n) {
        n = _n;
        info.assign(n, -1);
    }
 
    int get(int x) {
        if (info[x] < 0) return x;
        return info[x] = get(info[x]);
    }
 
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
 
        info[x] += info[y];
        info[y] = x;
 
        return true;    
    }
 
    bool connected(int x, int y) { return get(x) == get(y); }
};

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

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];
}

void fill_path(int u, int v) {
    int lca = query_lca(u, v);
    u = covering.get(u), v = covering.get(v);

    vector<int> path_edges;

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

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

    sort(all(path_edges));

    for (const auto &idx : path_edges) {
        if (ans[idx] == 0) 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);
    available_weight = 1;

    covering.init(N);

    for (int i = 0, j = 1; i < E; i++) {
        if (ans[i] != 0) continue;

        if (!keep[i])
            fill_path(edges[i].first, edges[i].second);

        ans[i] = available_weight++;
    }

    for (int i = 0; i < E; i++)
        cout << ans[i] << " ";
}

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

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

Compilation message

riggedroads.cpp: In function 'void solve()':
riggedroads.cpp:143:21: warning: unused variable 'j' [-Wunused-variable]
  143 |     for (int i = 0, j = 1; i < E; i++) {
      |                     ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 6 ms 7500 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 23072 KB Output is correct
2 Correct 140 ms 31004 KB Output is correct
3 Correct 161 ms 18468 KB Output is correct
4 Correct 191 ms 53396 KB Output is correct
5 Correct 224 ms 55344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 30556 KB Output is correct
2 Correct 70 ms 18116 KB Output is correct
3 Correct 36 ms 12880 KB Output is correct
4 Correct 86 ms 25864 KB Output is correct
5 Correct 34 ms 14912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 52896 KB Output is correct
2 Correct 316 ms 59636 KB Output is correct
3 Correct 72 ms 22220 KB Output is correct
4 Correct 115 ms 29580 KB Output is correct
5 Correct 373 ms 62908 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 38800 KB Output is correct
2 Correct 156 ms 30864 KB Output is correct
3 Correct 448 ms 59444 KB Output is correct
4 Correct 406 ms 56044 KB Output is correct
5 Correct 26 ms 11972 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7500 KB Output is correct
5 Correct 5 ms 7500 KB Output is correct
6 Correct 6 ms 7500 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 73 ms 23072 KB Output is correct
10 Correct 140 ms 31004 KB Output is correct
11 Correct 161 ms 18468 KB Output is correct
12 Correct 191 ms 53396 KB Output is correct
13 Correct 224 ms 55344 KB Output is correct
14 Correct 108 ms 30556 KB Output is correct
15 Correct 70 ms 18116 KB Output is correct
16 Correct 36 ms 12880 KB Output is correct
17 Correct 86 ms 25864 KB Output is correct
18 Correct 34 ms 14912 KB Output is correct
19 Correct 291 ms 52896 KB Output is correct
20 Correct 316 ms 59636 KB Output is correct
21 Correct 72 ms 22220 KB Output is correct
22 Correct 115 ms 29580 KB Output is correct
23 Correct 373 ms 62908 KB Output is correct
24 Correct 238 ms 38800 KB Output is correct
25 Correct 156 ms 30864 KB Output is correct
26 Correct 448 ms 59444 KB Output is correct
27 Correct 406 ms 56044 KB Output is correct
28 Correct 26 ms 11972 KB Output is correct
29 Correct 510 ms 53852 KB Output is correct
30 Correct 482 ms 55668 KB Output is correct
31 Correct 427 ms 54440 KB Output is correct
32 Correct 126 ms 18300 KB Output is correct
33 Correct 421 ms 55180 KB Output is correct