oj.uz

Submission #515860

# Submission time Handle Problem Language Result Execution time Memory
515860 2022-01-20T03:50:02 Z Joo Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 206 ms 12488 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4+10, LOG = 20;

int dis[N], dep[N], ta[LOG][N], V, Q;
vector<pair<int, int>> G[N];


void dfs(int u, int p){
    for(auto [v, w] : G[u]){
        if(v == p) continue;
        dis[v] = dis[u] + w;
        dep[v] = dep[u] + 1;
        ta[0][v] = u;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v); //what if u == v
    for(int k = LOG-1; k >= 0; k--) if(dep[ta[k][u]] >= dep[v]) u = ta[k][u];
    if(u == v) return u;
    for(int k = LOG-1; k >= 0; k--) if(ta[k][u] != ta[k][v]) u = ta[k][u], v = ta[k][v];
    return ta[0][u];
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> V;
    for(int i = 1; i < V; i++){
        int u, v, w; cin >> u >> v >> w;
        u++, v++;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    dep[1] = 1;
    dfs(1, -1);

    for(int k = 1; k < LOG; k++) for(int i = 1; i <= V; i++) ta[k][i] = ta[k-1][ta[k-1][i]];

    cin >> Q;
    while(Q--){
        int arr[10] = {}, cur[10] = {};

        for(int i = 0; i < 5; i++) cin >> arr[i], arr[i]++;
        int LC = arr[0], ans = 0;
        for(int i = 1; i < 5; i++) LC = lca(LC, arr[i]); // LC := lca of five nodes

        for(int bit = 1; bit < 32; bit++){ //32 = (1<<5)
            int cnt = 0, res = 0;
            for(int j = 0; j < 5; j++){
                if(bit&(1<<j)){
                    cur[cnt++] = j;
                }
            }

            if(cnt > 1){
                int lc = arr[cur[0]];
                for(int j = 1; j < cnt; j++){
                    lc = lca(lc, arr[cur[j]]);
                }                
                res = dis[lc] - dis[LC];
            } else {
                res = dis[arr[cur[0]]] - dis[LC];
            }

            if(cnt&1){
                ans += res;
            } else {
                ans -= res;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1500 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 10548 KB Output is correct
2 Correct 144 ms 12324 KB Output is correct
3 Correct 179 ms 12312 KB Output is correct
4 Correct 137 ms 12360 KB Output is correct
5 Correct 141 ms 12360 KB Output is correct
6 Correct 136 ms 12276 KB Output is correct
7 Correct 135 ms 12288 KB Output is correct
8 Correct 167 ms 12488 KB Output is correct
9 Correct 143 ms 12356 KB Output is correct
10 Correct 131 ms 12340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8388 KB Output is correct
2 Correct 28 ms 11364 KB Output is correct
3 Correct 26 ms 11364 KB Output is correct
4 Correct 26 ms 11332 KB Output is correct
5 Correct 31 ms 11348 KB Output is correct
6 Correct 29 ms 11364 KB Output is correct
7 Correct 25 ms 11356 KB Output is correct
8 Correct 26 ms 11340 KB Output is correct
9 Correct 29 ms 11348 KB Output is correct
10 Correct 25 ms 11332 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1500 KB Output is correct
2 Correct 200 ms 10548 KB Output is correct
3 Correct 144 ms 12324 KB Output is correct
4 Correct 179 ms 12312 KB Output is correct
5 Correct 137 ms 12360 KB Output is correct
6 Correct 141 ms 12360 KB Output is correct
7 Correct 136 ms 12276 KB Output is correct
8 Correct 135 ms 12288 KB Output is correct
9 Correct 167 ms 12488 KB Output is correct
10 Correct 143 ms 12356 KB Output is correct
11 Correct 131 ms 12340 KB Output is correct
12 Correct 28 ms 8388 KB Output is correct
13 Correct 28 ms 11364 KB Output is correct
14 Correct 26 ms 11364 KB Output is correct
15 Correct 26 ms 11332 KB Output is correct
16 Correct 31 ms 11348 KB Output is correct
17 Correct 29 ms 11364 KB Output is correct
18 Correct 25 ms 11356 KB Output is correct
19 Correct 26 ms 11340 KB Output is correct
20 Correct 29 ms 11348 KB Output is correct
21 Correct 25 ms 11332 KB Output is correct
22 Correct 202 ms 10536 KB Output is correct
23 Correct 141 ms 8764 KB Output is correct
24 Correct 160 ms 11844 KB Output is correct
25 Correct 150 ms 11696 KB Output is correct
26 Correct 206 ms 11748 KB Output is correct
27 Correct 152 ms 11700 KB Output is correct
28 Correct 141 ms 11748 KB Output is correct
29 Correct 188 ms 11724 KB Output is correct
30 Correct 190 ms 11904 KB Output is correct
31 Correct 143 ms 11736 KB Output is correct