Submission #1234082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234082		nasjes	Roadside Advertisements (NOI17_roadsideadverts)	C++20	30 / 100	75 ms	39084 KiB

roadsideadverts

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6 + 10;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, q;
ll t=0;
vector<pll> a[dim];
ll tin[dim], tout[dim], depth[dim], sum[dim];
ll marked[dim];
ll dp[dim], jump[dim][22];
void dfs(ll v, ll p, ll d, ll w){
    tin[v]=(++t);
    jump[v][0]=p;
    depth[v]=d;
    sum[v]=sum[p]+w;
    for(int st=1; st<=19; st++){
        jump[v][st]=jump[ jump[v][st-1] ][st-1];
    }
    for(auto x: a[v]){
        if(x.fi==p)continue;
        dfs(x.fi, v, d+1, x.se);
    }
    tout[v]=++t;
}
ll same(ll x, ll y){
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    swap(x, y);
    if(tin[x]<=tin[y] && tout[y]<=tout[x])return 1;
    return 0;
}
ll go(ll x, ll y){
    ll cur=x;
    if(same(x, y)){
        if(depth[x]<=depth[y])return x;
        else return y;
    }
    for(int i=19; i>=0; i--){
        if(!same(cur, y)){
            cur=jump[cur][i];
        }
    }
    cur=jump[cur][0];
    return cur;
}



int main() {
    cin>>n;
    for(int i=1; i<=n-1; i++){
        ll u, v, w;
        cin>>u>>v>>w;
        u++;
        v++;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    t=1;
    dfs(1, 1, 1, 0);
    cin>>q;
    while(q--){
        set<ll> cur;
        ll u;
        ll ans=0;
        for(int i=1; i<=5; i++){
            cin>>u;
            u++;
            cur.insert(u);
        }
        while(cur.size()!=1){
            vll pos;
            for(auto x: cur){
                pos.pb(x);
            }
            ll nw=0;
            ll sz=cur.size();
            ll p1,  p2, alca;
            for(int i=0; i<sz; i++){
                for(int j=0; j<sz; j++){
                   if(i==j)continue;
                    ll lca=go(pos[i], pos[j]);
                    if(depth[lca]>nw){
                        nw=depth[lca];
                        p1=pos[i];
                        p2=pos[j];
                        alca=lca;
                    }
                }
            }
            if(cur.find(p1)!=cur.end())cur.erase(p1);
            if(cur.find(p2)!=cur.end())cur.erase(p2);
            cur.insert(alca);
            ans+=(sum[p1]+sum[p2]-2*sum[alca]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

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