oj.uz

답안 #482049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482049 2021-10-22T18:12:40 Z PoPularPlusPlus Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 448 ms 62016 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 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 5 ms 7500 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 22712 KB Output is correct
2 Correct 105 ms 28344 KB Output is correct
3 Correct 107 ms 15424 KB Output is correct
4 Correct 174 ms 49836 KB Output is correct
5 Correct 150 ms 51756 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 30244 KB Output is correct
2 Correct 51 ms 18116 KB Output is correct
3 Correct 33 ms 12864 KB Output is correct
4 Correct 61 ms 25888 KB Output is correct
5 Correct 25 ms 14876 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 52064 KB Output is correct
2 Correct 313 ms 58680 KB Output is correct
3 Correct 56 ms 21860 KB Output is correct
4 Correct 93 ms 29192 KB Output is correct
5 Correct 304 ms 62016 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 38400 KB Output is correct
2 Correct 125 ms 29052 KB Output is correct
3 Correct 392 ms 60868 KB Output is correct
4 Correct 393 ms 57188 KB Output is correct
5 Correct 27 ms 11972 KB Output is correct

Subtask #7
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 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 5 ms 7500 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 55 ms 22712 KB Output is correct
10 Correct 105 ms 28344 KB Output is correct
11 Correct 107 ms 15424 KB Output is correct
12 Correct 174 ms 49836 KB Output is correct
13 Correct 150 ms 51756 KB Output is correct
14 Correct 89 ms 30244 KB Output is correct
15 Correct 51 ms 18116 KB Output is correct
16 Correct 33 ms 12864 KB Output is correct
17 Correct 61 ms 25888 KB Output is correct
18 Correct 25 ms 14876 KB Output is correct
19 Correct 233 ms 52064 KB Output is correct
20 Correct 313 ms 58680 KB Output is correct
21 Correct 56 ms 21860 KB Output is correct
22 Correct 93 ms 29192 KB Output is correct
23 Correct 304 ms 62016 KB Output is correct
24 Correct 211 ms 38400 KB Output is correct
25 Correct 125 ms 29052 KB Output is correct
26 Correct 392 ms 60868 KB Output is correct
27 Correct 393 ms 57188 KB Output is correct
28 Correct 27 ms 11972 KB Output is correct
29 Correct 405 ms 55460 KB Output is correct
30 Correct 448 ms 57344 KB Output is correct
31 Correct 371 ms 56248 KB Output is correct
32 Correct 95 ms 18440 KB Output is correct
33 Correct 370 ms 56804 KB Output is correct