제출 #1304404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304404		daniyar228	Drivers (BOI24_drivers)	C++20	100 / 100	121 ms	16832 KiB

Main

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

#define int long long
#define pb push_back

const int N=3e5+10;
const int mod=1e9+7;
const int inf=5e18;

int p[N],sz[N];

struct edge{int v,u,t;};

bool cmp(edge a,edge b) {
    return a.t<b.t;
}

struct queries{int a,b,p,idx;};

bool cmp1(queries a,queries b) {
    return a.p<b.p;
}

int leader(int x) {
    if(x==p[x]) return x;
    p[x]=leader(p[x]);
    return p[x]; 
}

void merge(int x,int y) {
    x=leader(x);
    y=leader(y);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    p[y]=x;
    sz[x]+=sz[y];
}

void solve() {
    int n,m,q;
    cin>>n>>m>>q;
    vector<edge>g(m+1);
    for(int i=1;i<=m;i++) {
        cin>>g[i].v>>g[i].u>>g[i].t;
    }
    for(int i=1;i<=n;i++)  {
        sz[i]=1;
        p[i]=i;
    }
    sort(g.begin()+1,g.end(),cmp);
    queries a[q+1];
    for(int i=1;i<=q;i++) {
        cin>>a[i].a>>a[i].b>>a[i].p;
        a[i].idx=i;
    }
    sort(a+1,a+q+1,cmp1);
    int j=1;
    int ans[q+1];
    for(int i=1;i<=q;i++) {
        while(j<=m && a[i].p>=g[j].t) {merge(g[j].v,g[j].u);j++;}
        ans[a[i].idx]=(leader(a[i].a)==leader(a[i].b));
    }
    for(int i=1;i<=q;i++) {
        if(ans[i]) cout<<"TAIP\n";
        else cout<<"NE\n";
    }
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T=1;
    // cin>>T;
    while(T--) solve();
} 

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