Submission #1154490

#TimeUsernameProblemLanguageResultExecution timeMemory
1154490LuvidiSightseeing (NOI14_sightseeing)C++20
15 / 25
2473 ms283604 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5;
int vw[2*maxn],du[2*maxn],ls,ch[2*maxn][2],id,ps[2*maxn];
pair<int,int> st[4*maxn][20];

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;
    ch[ls][0]=x,ch[ls][1]=y;
}

void dfs(int v,int d){
    ps[v]=id;
    st[id++][0]={d,vw[v]};
    if(ch[v][0]){
        dfs(ch[v][0],d+1);
        st[id++][0]={d,vw[v]};
        dfs(ch[v][1],d+1);
        st[id++][0]={d,vw[v]};
    }
}

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);
    }
    dfs(ls,0);
    for(int x=1;x<20;x++){
        for(int i=0;i+(1<<x)<=id;i++)st[i][x]=min(st[i][x-1],st[i+(1<<x-1)][x-1]);
    }
    while(q--){
        int x,y=ps[1];
        cin>>x;
        x=ps[x];
        if(x>y)swap(x,y);
        int z=31-__builtin_clz(y-x+1);
        cout<<min(st[x][z],st[y-(1<<z)+1][z]).second<<'\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...