Submission #776705

#	Time	Username	Problem	Language	Result	Execution time	Memory
776705		Cookie	Roadside Advertisements (NOI17_roadsideadverts)	C++14	7 / 100	39 ms	13512 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;
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];
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){
 	num[s] = cr++;
    for(auto i: adj[s]){
        if(i.fi == pre)continue;
        
        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;
        }
    }
}
ll 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);
        ll ans = 0;
        
        for(int j = 0; j < 5; j++){
            ans += find(a[j], a[(j + 1) % 5], true);
        }
        cout << ans / 2 << "\n";
        
    }
    
    return 0;
}

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