제출 #1154508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154508		Luvidi	관광 (NOI14_sightseeing)	C++20	15 / 25	3584 ms	260160 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][11];

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<11;x++){
        for(int i=0;i+(1<<2*x)<=id;i++){
            st[i][x]=min({st[i][x-1],st[i+(1<<2*x-2)][x-1],st[i+2*(1<<2*x-2)][x-1],st[i+3*(1<<2*x-2)][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))/2;
        pair<int,int> p={1e9,1e9};
        for(int i=0;i<4;i++){
            p=min(p,st[min(x,y-(1<<2*z)+1)][z]);
            x+=1<<2*z;
        }
        cout<<p.second<<'\n';
    }
}

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