Submission #1304426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304426		dbekarys	Drivers (BOI24_drivers)	C++20	0 / 100	3 ms	572 KiB

Main

#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;
    }
}

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