Submission #776707

#	Time	Username	Problem	Language	Result	Execution time	Memory
776707		Cookie	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	55 ms	13296 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
ifstream fin("measurement.in");
ofstream fout("measurement.out");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
const int mxn = 5e4 + 5;
struct th{
    int val = 0, sm = 0;
};
int n;
vt<pair<int, int>>adj[mxn + 3];
int depth[mxn + 3] = {0};
th up[mxn][17];
ll res = 0;
int num[mxn + 3] = {0};
int cr = 1;
bool cmp(int a, int b){
    return(num[a] < num[b]);
}
void dfs(int s, int pre){
 
    for(auto i: adj[s]){
        if(i.fi == pre)continue;
        num[i.fi] = cr++;
        int v = i.fi, c = i.se;
        depth[v] = depth[s] + 1;
        up[v][0].val = s; up[v][0].sm = c; 
        dfs(v, s);
    }
}
void build(){
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= n; j++){
            up[j][i].val = up[up[j][i - 1].val][i - 1].val;
            up[j][i].sm = up[j][i - 1].sm + up[up[j][i - 1].val][i - 1].sm;
        }
    }
}
int find(int a, int b, bool ok){
    if(depth[a] < depth[b])swap(a, b);
    int k =depth[a] - depth[b];
    ll curr = 0;
    for(int i = 0; i < 17; i++){
        if(k & (1 << i)){
            curr += up[a][i].sm;
            a = up[a][i].val;
        }
    }
    //cout << curr << " ";
    if(a == b){
        if(ok)return(curr);
        return(a);
    }
    for(int i = 16; i >= 0; i--){
        if(up[a][i].val != up[b][i].val){
            curr += up[a][i].sm + up[b][i].sm;
            a = up[a][i].val; b = up[b][i].val;
        }
    }
    curr += up[a][0].sm + up[b][0].sm;
    if(ok)return(curr);
    return(up[a][0].val);
}
int main()
{
    LIFESUCKS;
    cin >> n;
    
    for(int i = 1; i < n; i++){
        int u, v, c; cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
    dfs(0, -1);
    build();
    int a[5];
    int q; cin >> q;
    
    for(int i = 0; i < q; i++){
        for(int j = 0; j < 5; j++)cin >> a[j];
        sort(a, a + 5, cmp);
        int lca = find(a[1], a[0], false);
        
        for(int j = 2; j < 5; j++){
            lca = find(lca, a[j], false);
        }
        res = find(lca, a[0], true);
        
        for(int j = 1; j < 5; j++){
            
            res += find(a[j], find(a[j - 1], a[j], false), true);
            //cout << a[j] << " " << find(a[j], a[j - 1], false) << " " << res << "\n";
        }
        cout << res << "\n";
        
    }
    
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30