제출 #1326048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326048		nminhnguyenle	Drivers (BOI24_drivers)	C++20	100 / 100	122 ms	21504 KiB

Main

// NAM MÔ A DI ĐÀ PHẬT

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")

// defines
#define int long long
#define inf LLONG_MAX/20
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define fr front
#define bk back
#define fi first
#define se second

// typedefs
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<string, ll> psi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;

// dsu template
struct ufds{
	vector<int> par, sz;
	ufds(int n){
		par.resize(n+1,0); // resize parents array and init. to 0
		sz.resize(n+1,1); // sizes of the sets, init. all to 1
		for(int i=1;i<=n;i++){
			par[i]=i; // every parent is itself
		}
	}
	int find_par(int u){ // find parent node
		if(par[u]==u){
			return u;
		}
		return par[u]=find_par(par[u]); // path compression
	}
	int unite(int x, int y){ // uniting set x and y
		x=find_par(x);
		y=find_par(y);
		if(x==y) return 0;
		if(sz[x]>sz[y]) swap(x,y); // swap from large to small (merge small into large)
		par[x]=y; // set parent
		sz[y]+=sz[x]; // update set sizes
		return true;
	}
};

signed main(){
    fastio();
    int n,m,u;
    cin>>n>>m>>u;
    vector<array<int,3>> r(m);
    for(int i=0;i<m;i++){
		int x,y,t;
		cin>>x>>y>>t;
		r[i]={t,x,y};
	}
	vector<array<int,4>> q(u);
	for(int i=0;i<u;i++){
		int a,b,p;
		cin>>a>>b>>p;
		q[i]={p,a,b,i};
	}
	sort(r.begin(),r.end());
	sort(q.begin(),q.end());
    ufds dsu(n+1);
    int p=0;
    vector<string> ans(u);
    for(int i=0;i<u;i++){
        while(p<m && r[p][0]<=q[i][0]){
            dsu.unite(r[p][1],r[p][2]);
            p++;
        }
        if(dsu.find_par(q[i][1])==dsu.find_par(q[i][2])){
            ans[q[i][3]]="TAIP";
        }
        else{
            ans[q[i][3]]="NE";
        }
    }
    for(string i:ans){
        cout<<i<<'\n';
    }
    return 0;
}

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