Submission #1009437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009437		imarn	Drivers (BOI24_drivers)	C++14	100 / 100	202 ms	60580 KiB

Main

#include<bits/stdc++.h>
//#include "gap.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int mxn=2e5+5;
int pr[mxn];
vector<pii>g[mxn];
bool vis[mxn]{0};
int d[mxn]{0};
int up[mxn][20]{0},dp[mxn][20]{0};
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
void dfs(int u,int p,int l){
    d[u]=l;up[u][0]=p;vis[u]=1;
    for(int i=1;i<20;i++)up[u][i]=up[up[u][i-1]][i-1];
    for(auto v:g[u]){
        if(vis[v.f])continue;
        dp[v.f][0]=v.s;dfs(v.f,u,l+1);
    }
}
int qr(int a,int b,int res=0){
    if(d[a]>d[b])swap(a,b);
    for(int i=19;i>=0;i--)if(d[b]-(1<<i)>=d[a])res=max(res,dp[b][i]),b=up[b][i];
    if(a==b)return res;
    for(int i=19;i>=0;i--)if(up[a][i]!=up[b][i])res=max({res,dp[a][i],dp[b][i]}),a=up[a][i],b=up[b][i];
    return max({res,dp[a][0],dp[b][0]});
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    vector<pair<int,pii>>ed;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        ed.pb({c,{a,b}});
    }sort(ed.begin(),ed.end());iota(pr,pr+n+1,0);
    for(auto it : ed){
        if(get(it.s.f)==get(it.s.s))continue;
        pr[get(it.s.f)]=get(it.s.s);
        g[it.s.f].pb({it.s.s,it.f});g[it.s.s].pb({it.s.f,it.f});
    }
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        dfs(i,i,0);
    }
    for(int j=1;j<20;j++)for(int i=1;i<=n;i++)dp[i][j]=max(dp[i][j-1],dp[up[i][j-1]][j-1]);
    while(q--){
        int a,b,p;cin>>a>>b>>p;
        if(get(a)!=get(b))cout<<"NE\n";
        else cout<<(qr(a,b)<=p?"TAIP\n":"NE\n");
    }
}

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