oj.uz

Submission #362588

# Submission time Handle Problem Language Result Execution time Memory
362588 2021-02-03T17:17:33 Z wind_reaper Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 56 ms 9768 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int64_t>>> adj;
struct LCA{
    vector<vector<int>> up; 
    int l;
    vector<int> tin, tout; 
    vector<int64_t> depth;
    LCA(int n){
        l = 32 - __builtin_clz(n);
        up.resize(l+1, vector<int>(n));
        tin.resize(n); 
        tout.resize(n);
        depth.resize(n);
        dfs(0, 0, 0);
    }
    int timer = 0; 
    void dfs(int node, int par, int64_t W){
        tin[node] = timer++; 
        depth[node] = depth[par] + W;
        up[0][node] = par;
        for(int i = 1; i <= l; i++)
            up[i][node] = up[i-1][up[i-1][node]];

        for(auto&[v, w] : adj[node]){
            if(v == par)
                continue;
            dfs(v, node, w);
        }

        tout[node] = timer++;
    }

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

    int lca(int u, int v){
        if(isAncestor(u, v))
            return u;
        if(isAncestor(v, u))
            return v;

        for(int i = l; i >= 0; --i)
            if(!isAncestor(up[i][u], v))
                u = up[i][u];

        return up[0][u];
    }

    int64_t dist(int u, int v){
        int L = lca(u, v); 
        return depth[u] + depth[v] - 2*depth[L];
    }
}; 
int32_t main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
        
    int n;
    cin >> n; 

    adj.resize(n); 

    for(int i = 0; i < n-1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w); 
    }

    LCA d(n);
    int Q;
    cin >> Q; 
    for(int _ = 0; _ < Q; _++){
        vector<int> q(5);
        for(int i = 0; i < 5; i++)
            cin >> q[i];

        int64_t ans = 0; 

        for(int i = 0; i < 5; i++){
            int64_t w = d.dist(d.lca(q[(i+4)%5], q[i]), q[i]);
            ans += w;
        }

        cout << ans << '\n';
    }
    return 0; 
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 56 ms 9768 KB Output isn't correct
3 Halted 0 ms 0 KB -