Submission #1223511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223511		minhpk	Roadside Advertisements (NOI17_roadsideadverts)	C++20	100 / 100	64 ms	63816 KiB

roadsideadverts

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>> z[1000005];
int logarit[1000005];
int sta[1000005];
int fin[1000005];
int euler[1000005];
int tour;

int dist[1000005];
int high[1000005];
int st[800001][20];
void dfs(int i,int par){

    tour++;
    sta[i]=tour;
    euler[tour]=i;

    for (auto p:z[i]){
         if (p.first==par){
            continue;
         }
         high[p.first]=high[i]+1;
         dist[p.first]=dist[i]+p.second;
         dfs(p.first,i);
         tour++;
         euler[tour]=i;
    }

    tour++;
    euler[tour]=i;
    fin[i]=tour;
}


void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}

int lca(int x,int y){
    int l = min(sta[x], sta[y]);
    int r = max(sta[x], sta[y]);
    int j = logarit[r - l + 1];
    int idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}
vector <int> v;
bool cmp(int a,int b){
    return sta[a]<sta[b];
}


int calc(int x,int y){
//    if (x==1 && y==2){
//        cout << dist[x] << " " << dist[y] << " " << lca(x,y) << "\n";
//    }
    return dist[x]+dist[y]-2*dist[lca(x,y)];
}

int duongkinh(){

    int pos=v[0];
    int dis=0;
    for (int i=1;i<v.size();i++){
         if (dis<calc(v[0],v[i])){
             dis=calc(v[0],v[i]);
             pos=v[i];
         }
    }

    int pos1=pos;
    int dis1=0;

    for (int i=0;i<v.size();i++){
         if (dis1<calc(pos,v[i])){
             dis1=calc(pos,v[i]);
             pos1=v[i];
         }
    }
    return calc(pos,pos1);
}



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a;
    cin >> a;
    for (int i=1;i<a;i++){
         int x,y,t;
         cin >> x >> y >> t;
         z[x].push_back({y,t});
         z[y].push_back({x,t});
    }

    logarit[2] = 1;
    for(int i = 3; i <= 1000000; i++){
         logarit[i] = logarit[i/2] + 1;
    }
    dfs(0,-1);
    buildst();

    int c;
    cin >> c;
    while (c--){
        int a1,a2,a3,a4,a5;
        cin >> a1 >> a2 >> a3 >>a4 >> a5;
        v.push_back(a1);
        v.push_back(a2);
        v.push_back(a3);
        v.push_back(a4);
        v.push_back(a5);
        sort(v.begin(),v.end(),cmp);
        int res=0;
        int l=v[0];
        for (int i=0;i+1<v.size();i++){
             l=lca(l,v[i+1]);
             res+=calc(v[i],v[i+1]);
//             cout << v[i] << " " << v[i+1] << "\n";

        }
        res+=calc(l,v[0]);

        res+=calc(l,v[4]);
        cout << res/2 << "\n";


        v.clear();
    }
    return 0;
}

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