oj.uz

Submission #487457

# Submission time Handle Problem Language Result Execution time Memory
487457 2021-11-15T15:20:48 Z KienTran Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 195 ms 57400 KB 
#include <bits/stdc++.h>

using namespace std;

const int O = 5e5 + 5;
const int inf = 1e9;

int n, q, c[O], h[O], E[O], W[O], deg[O], p[18][O], f[18][O];
vector <int> g[O];

bool sub2 = true;

void init(int u, int par = 0){
    for (int i : g[u]){
        int v = u ^ E[i];
        int w = W[i];

        if (v != par){
            h[v] = h[u] + 1;
            c[h[u]] += w;
            c[h[v]] += c[h[u]];
            init(v, u);
        }
    }
}

void dfs(int u, int par = 0){
    for (int i : g[u]){
        int v = u ^ E[i];
        int w = W[i];

        if (v != par){
            h[v] = h[u] + 1;
            p[0][v] = u;
            f[0][v] = w;
            dfs(v, u);
        }
    }
}

void BuildLca(){
    memset(p, -1, sizeof(p));

    dfs(1);
    for (int i = 1; i <= 17; ++ i){
        for (int j = 1; j <= n; ++ j){
            if (p[i - 1][j] != -1){
                p[i][j] = p[i - 1][p[i - 1][j]];
                f[i][j] = f[i - 1][j] + f[i - 1][p[i - 1][j]];
            }
        }
    }
}

int Lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);

    for (int i = 17; i >= 0; -- i){
        if (h[u] - (1 << i) >= h[v]) u = p[i][u];
    }

    if (u == v) return u;

    for (int i = 17; i >= 0; -- i){
        if (p[i][u] != p[i][v]){
            u = p[i][u];
            v = p[i][v];
        }
    }

    return p[0][u];
}

int Jump(int u, int d){
    int res = 0;
    for (int i = 17; i >= 0; -- i){
        if (d >> i & 1){
            res += f[i][u];
            u = p[i][u];
        }
    }
    return res;
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++ i){
        int u, v, w; cin >> u >> v >> w;
        u += 1; v += 1;
        g[u].push_back(i);
        g[v].push_back(i);

        E[i] = u ^ v;
        W[i] = w;

        deg[u] += 1;
        deg[v] += 1;

        sub2 &= deg[u] <= 2;
        sub2 &= deg[v] <= 2;
    }

    if (sub2){
        int sta;
        for (int i = 1; i <= n; ++ i)
            if (deg[i] == 1) sta = i;

        h[sta] = 1;
        init(sta);

        cin >> q;
        for (int i = 1; i <= q; ++ i){
            int node[5];
            for (int j = 0; j < 5; ++ j) cin >> node[j], node[j] += 1;

            int Min = inf, Max = -inf;
            for (int j = 0; j < 5; ++ j){
                Min = min(Min, h[node[j]]);
                Max = max(Max, h[node[j]]);
            }

            cout << c[Max - 1] - c[Min - 1] << "\n";
        }

        return 0;
    }

    BuildLca();

    cin >> q;
    for (int i = 1; i <= q; ++ i){
        int node[5];
        for (int j = 0; j < 5; ++ j) cin >> node[j], node[j] += 1;

        int lca = node[0];
        for (int j = 1; j < 5; ++ j) lca = Lca(lca, node[j]);

        int res = 0;
        for (int j = 1; j < 32; ++ j){
            int par, cnt = 0;
            for (int z = 0; z < 5; ++ z)
                if (j >> z & 1) par = node[z], cnt += 1;

            for (int z = 0; z < 5; ++ z)
                if (j >> z & 1) par = Lca(node[z], par);

            if (cnt & 1) res += Jump(par, h[par] - h[lca]);
            if (!(cnt & 1)) res -= Jump(par, h[par] - h[lca]);
        }

        cout << res << "\n";
    }
}

Compilation message

roadsideadverts.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~
roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:146:42: warning: 'par' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |                 if (j >> z & 1) par = Lca(node[z], par);
      |                                       ~~~^~~~~~~~~~~~~~
roadsideadverts.cpp:110:13: warning: 'sta' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |         init(sta);
      |         ~~~~^~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 19656 KB Output is correct
2 Correct 34 ms 19604 KB Output is correct
3 Correct 41 ms 19680 KB Output is correct
4 Correct 34 ms 19668 KB Output is correct
5 Correct 33 ms 19656 KB Output is correct
6 Correct 34 ms 19660 KB Output is correct
7 Correct 33 ms 19600 KB Output is correct
8 Correct 35 ms 19568 KB Output is correct
9 Correct 35 ms 19612 KB Output is correct
10 Correct 37 ms 19640 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 51584 KB Output is correct
2 Correct 46 ms 56876 KB Output is correct
3 Correct 51 ms 56964 KB Output is correct
4 Correct 56 ms 56892 KB Output is correct
5 Correct 48 ms 56936 KB Output is correct
6 Correct 51 ms 56988 KB Output is correct
7 Correct 55 ms 56904 KB Output is correct
8 Correct 48 ms 57000 KB Output is correct
9 Correct 47 ms 56884 KB Output is correct
10 Correct 48 ms 56924 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Correct 36 ms 19656 KB Output is correct
3 Correct 34 ms 19604 KB Output is correct
4 Correct 41 ms 19680 KB Output is correct
5 Correct 34 ms 19668 KB Output is correct
6 Correct 33 ms 19656 KB Output is correct
7 Correct 34 ms 19660 KB Output is correct
8 Correct 33 ms 19600 KB Output is correct
9 Correct 35 ms 19568 KB Output is correct
10 Correct 35 ms 19612 KB Output is correct
11 Correct 37 ms 19640 KB Output is correct
12 Correct 41 ms 51584 KB Output is correct
13 Correct 46 ms 56876 KB Output is correct
14 Correct 51 ms 56964 KB Output is correct
15 Correct 56 ms 56892 KB Output is correct
16 Correct 48 ms 56936 KB Output is correct
17 Correct 51 ms 56988 KB Output is correct
18 Correct 55 ms 56904 KB Output is correct
19 Correct 48 ms 57000 KB Output is correct
20 Correct 47 ms 56884 KB Output is correct
21 Correct 48 ms 56924 KB Output is correct
22 Correct 30 ms 19636 KB Output is correct
23 Correct 127 ms 51940 KB Output is correct
24 Correct 186 ms 57288 KB Output is correct
25 Correct 163 ms 57308 KB Output is correct
26 Correct 195 ms 57400 KB Output is correct
27 Correct 189 ms 57400 KB Output is correct
28 Correct 175 ms 57376 KB Output is correct
29 Correct 182 ms 57244 KB Output is correct
30 Correct 177 ms 57264 KB Output is correct
31 Correct 168 ms 57400 KB Output is correct