제출 #1304426

#제출 시각아이디문제언어결과실행 시간메모리
1304426dbekarysDrivers (BOI24_drivers)C++20
0 / 100
3 ms572 KiB
#include <bits/stdc++.h>
#define int long long
#define pll pair<int,int>
#define endl '\n'
using namespace std;
const int MOD2=998244353;
const int MOD1=1e9+7;
const int N=3e5+7;
const int LOG=20;
const long long inf=8e18+7;
vector<int>g[N];
int p[N],col[N];
struct st {
    int f,s,x;
    int ix;
};
int get(int x){
    if(p[x]==x) return x;
    return p[x]=get(p[x]);
}
int uni(int l,int r){
    l=get(l);
    r=get(r);
    if(l==r) return 0;
    if(col[l]<col[r])
        swap(l,r);
    p[r]=l;
    col[l]+=col[r];
    return 1;
}
bool cmp(st i,st j){
    return i.x<j.x;
}
signed main()
{
    ios_base::sync_with_stdio(0),
    cin.tie(0);
    int n,m,q;
    cin>> n>>m>>q;
    for(int i=1;i<=n;i++){
        p[i]=i;
        col[i]=1;
    }
    vector<st>v(m),vq(m);
    for(int i=0;i<m;i++){
        cin>> v[i].f>>v[i].s>>v[i].x;
    }
    sort(v.begin() , v.end() , cmp);
    for(int i=0;i<q;i++){
        cin>> vq[i].f>>vq[i].s>>vq[i].x;
        vq[i].ix=i;
    }
    sort(vq.begin() , vq.end() , cmp);
    int k=0;
    string ans[q];
    for(int j=0;j<q;j++){
        int a=vq[j].f,b=vq[j].s,pr=vq[j].x;
        for(int i=k;i<m;i++)
            if(v[i].x<=pr)
                uni(v[i].f,v[i].s),k=i+1;
        if(get(a)==get(b)){
            ans[vq[j].ix]="TAIP";
        }
        else {
            ans[vq[j].ix]="NE";
        }
    }
    for(int i=0;i<q;i++){
        cout<< ans[i]<<endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...