Submission #1304443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304443		the_ZHER	Drivers (BOI24_drivers)	C++20	10 / 100	63 ms	5424 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;
};
vector<pair<int,int> >v[N];
vector<edge>v1;
int pr[N];
int us[N];
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[a]=b;
}
int in[N],out[N];
int up[N][20];
int mn[N][20];
int cnt[N];
int tim=1;
void dfs(int n,int pr,int z){
    up[n][0]=pr;
    mn[n][0]=z;
    in[n]=tim;
    tim++;
    us[n]=1;
    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);
        }
    }
    out[n]=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){
    if(x==pr){
        return 0;
    }
    int ans=0;
    for(int i=19;i>=0;i--){
        if(!ch(up[x][i],pr)){
            ans=max(ans,mn[x][i]);
            x=up[x][i];
        }
    }
    return max(ans,mn[x][0]);
}
int f(int x,int y){
    if(ch(x,y)==1){
        return solve(y,x);
    }
    if(ch(y,x)==1){
        return solve(x,y);
    }
    int z=x;
    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(z,c),solve(y,c));
} 
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    int n,m,u;
    cin>>n>>m>>u;
    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});
        }
    }
    for(int i=1;i<=n;i++){
        if(us[i]==0){
            dfs(i,i,0);
            tim=1;
        }
    }
    for(int i=1;i<=u;i++){
        int x,y,p;
        cin>>x>>y>>p;
        if(get(x)!=get(y)){
            cout<<"NE\n";
            continue;
        }
        if(x==y){
            cout<<"TAIP\n";
            continue; 
        }
        int ans=f(x,y);
        if(ans<=p){
            cout<<"TAIP\n";
        }else{
            cout<<"NE\n";
        }
    }
}

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