提出 #66600602

---

ソースコード 拡げる

#include <bits/stdc++.h>

//pair
#define int long long
#define PII pair <int, int>
#define PIII pair <int, PII>

//vector
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

//other
#define gcd __gcd
#define x first
#define y second

using namespace std;
namespace lhz{
	using T = int;
	inline T read(){
		T res = 0, f = 1;
		char ch = getchar();
		if(ch == '-') f = -1, ch = getchar();
		while (ch >= '0' && ch <= '9')
			res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
		return res * f;
	}
	
	inline void write(T n){
		if (n < 0) putchar('-'), n *= -1;
		if (n > 9) write(n / 10);
		putchar(n % 10 + '0');
	}
}

using ll = long long;
using db = double;
const int inf = 0x3f3f3f3f;
const double eps = 1e-4;
const int mod = 1e8, N = 1e5 + 5;

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono :: steady_clock :: now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

bool ep (const double a, const double b){
	return fabs(a - b) > eps;
}

template <typename T>
void cmax (T &a, T b){
	a = (a > b ? a : b);
}

template <typename T>
void cmin (T &a, T b){
	a = (a < b ? a : b);
}

template <typename T>
void Swap (T &a, T &b){
	a = a ^ b, b = a ^ b, a = a ^ b;
}

int qmi (int a, int n, int p){
	int res = 1;
	while (n){
		if(n & 1) res = res * a % p;
		a = a * a % p, n >>= 1;
	}
	return res;
}

int inv (int a, int p){
	return qmi(a, p - 2, p);
}

int lcm (int a, int b){
	return a * b / gcd(a, b);
}

int re (int a){
	return (a ^ (-1)) + 1;
}

int sabs (int a){
	return (a ^ (a >> 31)) - (a >> 31);
}

//#define int long long
int n, q;
int p[N], scc_cnt; // DSU
PII point[N];
priority_queue <PIII, vector <PIII> , greater <PIII>> heap; // distance

int dis (PII a, PII b){
	return abs (a.x - b.x) + abs (a.y - b.y);
}

int find (int x){
	return (p[x] == x ? x : (p[x] = find (p[x])));
}

void sovle (){
	cin >> n >> q, scc_cnt = n;
	for (int i = 1; i <= n; i ++ ) cin >> point[i].x >> point[i].y, p[i] = i;
	
	for (int i = 1; i <= n; i ++ ) for (int j = i + 1; j <= n; j ++ ) heap.emplace (dis (point[i], point[j]), make_pair (i, j));
	
	while (q -- ){
		int op; cin >> op;
		if (op == 1){
			int a, b; cin >> a >> b;
			
			point[ ++ n] = make_pair (a, b), scc_cnt ++ , p[n] = n;
			for (int i = 1; i < n; i ++ ) heap.emplace (dis (point[i], point[n]), make_pair (i, n));
		} else if (op == 2){
			if (scc_cnt == 1){
				cout << "-1\n";
				continue;
			}
			
			int mn = inf;
//			if (!q) cerr << heap.size () << '\n';
			while (heap.size () && heap.top ().x <= mn) {
//				if (!q) cerr << " --- " << mn << ' ' << heap.size () << ' ' << heap.top ().x << ' ';
				PIII t = heap.top (); heap.pop ();
				
				int fu = find (t.y.x), fv = find (t.y.y);
//				cerr << fu << ' ' << fv << '\n';
				if (fu != fv) mn = t.x, p[fv] = fu, scc_cnt -- ;
			}
			
			cout << mn << '\n';
		} else {
			int u, v; cin >> u >> v;
			cout << (find (u) == find (v) ? "Yes\n" : "No\n");
		}
		
//		cout << " *** " << heap.size () << '\n';
	}
}
#undef int

signed main (){
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	
	cin.tie(nullptr) -> sync_with_stdio(false);
	
	int T = 1;
//	cin >> T;
	while(T -- ) sovle();
	return 0;
}

提出情報

ジャッジ結果