Submission #1111359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111359		yhkhoo	Drivers (BOI24_drivers)	C++17	100 / 100	127 ms	7752 KiB

Main

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

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, pii> ppp;
#define fi first
#define se second

const int MAXN = 200005;
int p[MAXN];
int get_parent(int x){
	if(p[x] == x) return x;
	p[x] = get_parent(p[x]);
	return p[x];
}
void union_set(int u, int v){
	u = get_parent(u);
	v = get_parent(v);
	if(u==v) return;
	p[u] = v;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int n, m, u;
	cin >> n >> m >> u;
	deque<pip> r;
	for(int i=0; i<m; i++){
		pip tmp;
		cin >> tmp.se.fi >> tmp.se.se >> tmp.fi;
		r.push_back(tmp);
	}
	sort(r.begin(), r.end());
	deque<ppp> c;
	for(int i=0; i<u; i++){
		ppp tmp;
		cin >> tmp.se.fi >> tmp.se.se >> tmp.fi.fi;
		tmp.fi.se = i;
		c.push_back(tmp);
	}
	sort(c.begin(), c.end());
	for(int i=1; i<=n; i++){
		p[i] = i;
	}
	vector<bool> ans(u, 0);
	for(auto i: c){
		while(r.size() && r.front().fi <= i.fi.fi){
			union_set(r.front().se.fi, r.front().se.se);
			r.pop_front();
		}
		ans[i.fi.se] = get_parent(i.se.fi) == get_parent(i.se.se);
	}
	for(auto i: ans){
		if(i){
			cout << "TAIP\n";
		}
		else{
			cout << "NE\n";
		}
	}
	return 0;
}
		
		
	

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