Submission #521424

#	Time	Username	Problem	Language	Result	Execution time	Memory
521424		niloyroot	Roadside Advertisements (NOI17_roadsideadverts)	C++14	7 / 100	49 ms	15576 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1000000007;
const ll maxn = 50005;
ll n,sz,tim=0,cnt=0;
vector<pl> adj[maxn];
ll up[maxn][20];
ll tin[maxn];
ll tout[maxn];
ll order[maxn];
ll depth[maxn];

void dfs(ll i, ll pa){
    order[i]=cnt++;
    tin[i]=tim++;
    up[i][0]=pa;
    forp(j,1,sz){
        up[i][j]=up[up[i][j-1]][j-1];
    }
    for(auto u:adj[i]){
        if(u.ff!=pa){
            depth[u.ff]=depth[i]+u.ss;
            dfs(u.ff,i);
        }
    }
    tout[i]=tim++;
}

bool is_anc(ll u, ll v){
    return (tin[v]<=tin[u] && tout[u]<=tout[v]);
}

ll lca(ll u, ll v){
    if(is_anc(u,v)){
        return v;
    }
    if(is_anc(v,u)){
        return u;
    }
    forn(i,sz,1){
        if(!is_anc(v,up[u][i])){
            u=up[u][i];
        }
    }
    return up[u][0];
}

void solve(){
    cin>>n; sz=ceil(log2(n));
    forp(i,1,n-1){
        ll u,v,w; cin>>u>>v>>w; u++;v++;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dfs(1,1);

    ll q; cin>>q;
    forp(i,1,q){
        ll a[5];
        forp(j,0,4){
            cin>>a[j]; a[j]++;
        }
        sort(a,a+4,[](ll u, ll v){
            return order[u]<order[v];
        });
        ll sum=0;
        forp(j,0,4){
            sum+=(depth[a[j]]+depth[a[(j+1)%5]]-2*depth[lca(a[j],a[(j+1)%5])]);
        }
        cout<<sum/2<<newl;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1; //cin>>t;
    while(t--)solve();
}

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