Submission #1154488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154488		Luvidi	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	3503 ms	156968 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5;
int vw[2*maxn],du[2*maxn],ls,up[2*maxn][20],ch[2*maxn][2],dt[2*maxn];

int rp(int x){
    if(x==du[x])return x;
    return du[x]=rp(du[x]);
}

void jn(int x,int y,int v){
    x=rp(x);y=rp(y);
    if(x==y)return;
    du[x]=++ls;
    du[y]=ls;
    vw[ls]=v;
    up[x][0]=up[y][0]=up[ls][0]=ls;
    ch[ls][0]=x,ch[ls][1]=y;
}

void dfs(int v){
    if(ch[v][0]){
        dt[ch[v][0]]=dt[ch[v][1]]=dt[v]+1;
        dfs(ch[v][0]);
        dfs(ch[v][1]);
    }
}

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    pair<int,pair<int,int>> ed[m];
    for(int i=0;i<m;i++)cin>>ed[i].second.first>>ed[i].second.second>>ed[i].first;
    sort(ed,ed+m);
    reverse(ed,ed+m);
    iota(du,du+2*n,0);
    ls=n;
    for(auto[w,p]:ed){
        auto[u,v]=p;
        jn(u,v,w);
    }
    for(int x=1;x<20;x++){
        for(int i=1;i<2*n;i++)up[i][x]=up[up[i][x-1]][x-1];
    }
    dfs(ls);
    while(q--){
        int x;
        cin>>x;
        int y=1;
        if(dt[x]>dt[y])swap(x,y);
        for(int i=19;i>-1;i--)if(dt[y]-(1<<i)>=dt[x])y=up[y][i];
        for(int i=19;i>-1;i--)if(up[x][i]!=up[y][i])x=up[x][i],y=up[y][i];
        if(x!=y)x=up[x][0];
        cout<<vw[x]<<'\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10