Submission #1304414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304414		the_ZHER	Drivers (BOI24_drivers)	C++20	0 / 100	3 ms	576 KiB

Main

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

#define int long long
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=2e5+10;
const int inf=1e18;
const int mod=1e9+7;
struct edge{
    int x,y,w;
};
int n,m,u;
vector<pair<int,int> >v[N];
vector<edge>v1;
int pr[N];
int pw[30];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int get(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x]=get(pr[x]);
}
void unio(int x,int y){
    int a=get(x);
    int b=get(y);
    if(a==b){
        return;
    }
    pr[b]=pr[a];
}
int in[N],out[N];
int up[N][20];
int mn[N][20];
int cnt[N];
int tim=0;
void dfs(int n,int pr,int z,int cnt1){
    up[n][0]=pr;
    mn[n][0]=z;
    in[n]=tim;
    tim++;
    cnt[n]=cnt1;
    for(int i=1;i<20;i++){
        up[n][i]=up[up[n][i-1]][i-1];
        mn[n][i]=max(mn[n][i-1],mn[up[n][i-1]][i-1]);
    }
    for(int i=0;i<v[n].size();i++){
        if(v[n][i].first!=pr){
            dfs(v[n][i].first,n,v[n][i].second,cnt1+1);
        }
    }
    out[n]=tim;
    tim++;
}
int ch(int x,int y){
    if(in[x]<=in[y]&&out[x]>=out[y]){
        return 1;
    }
    return 0;
}
int solve(int x,int pr){
    int cnt1=cnt[x]-cnt[pr];
    int ans=0;
    for(int i=19;i>=0;i--){
        if(cnt1>=pw[i]){
            cnt1-=pw[i];
            ans=max(ans,mn[x][i]);
            x=up[x][i];
        }
    }
    return ans;
}
int f(int x,int y){
    if(ch(x,y)==1){
        return solve(y,x);
    }
    if(ch(y,x)==1){
        return solve(x,y);
    }
    for(int i=19;i>=0;i--){
        if(ch(up[x][i],y)==1){
            x=up[x][i];
        }
    }
    int c=up[x][0];
    return max(solve(x,c),solve(y,c));
} 
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cin>>n>>m>>u;
    pw[0]=1;
    for(int i=1;i<=25;i++){
        pw[i]=pw[i-1]*2;
    }
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        v1.push_back({x,y,w});
    }
    for(int i=1;i<=n;i++){
        pr[i]=i;
    }
    sort(v1.begin(),v1.end(),cmp);
    for(int i=0;i<v1.size();i++){
        int x=get(v1[i].x);
        int y=get(v1[i].y);
        if(x!=y){
            unio(v1[i].x,v1[i].y);
            v[v1[i].x].push_back({v1[i].y,v1[i].w});
            v[v1[i].y].push_back({v1[i].x,v1[i].w});
        }
    }
    dfs(1,0,0,0);
    for(int i=1;i<=u;i++){
        int x,y,p;
        cin>>x>>y>>p;
        int a=get(x);
        int b=get(y);
        if(a!=b){
            cout<<"NE\n";
            continue;
        }
        int ans=f(x,y);
        if(ans<=p){
            cout<<"TAIP\n";
        }else{
            cout<<"NE\n";
        }
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45