Submission #1154490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154490		Luvidi	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	2473 ms	283604 KiB

sightseeing

#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';
    }
}

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