提出 #66566245

---

ソースコード 拡げる

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MaxN 3005

struct Node {
	int dis, u, v;
	bool operator < (Node t) const {
		return dis < t.dis;
	}
	bool operator > (Node t) const {
		return dis > t.dis;
	}
};

int fa[MaxN], n, m, q, x[MaxN], y[MaxN];
priority_queue < Node, vector<Node>, greater<Node> > pq;

int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

void add(int j) {
	for(int i = 1; i < j; i++) {
		Node t;
		t.dis = abs(x[i]-x[j]) + abs(y[i]-y[j]);
		t.u = i;
		t.v = j;
		pq.push(t);
	}
}

int main()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		m++;
		fa[i] = i;
		cin >> x[i] >> y[i];
		add(i);
	}
	int op;
	while (q--) {
		cin >> op;
		if (op == 1) {
			n++;
			m++;
			fa[n] = n;
			cin >> x[n] >> y[n];
			add(n);
		}
		else if (op == 2) {
			if (m == 1) cout << -1 << endl;
			else {
				int now = -1;
				while(now == -1) {
					Node t = pq.top();
					pq.pop();
					if (find(t.u) == find(t.v)) continue;
					now = t.dis;
					cout << now << endl;
					fa[find(t.u)] = find(t.v);
					m--;
					while (!pq.empty() && pq.top().dis == now) {
						Node tt = pq.top();
						pq.pop();
						if (find(tt.u) != find(tt.v)) {
							fa[find(tt.u)] = find(tt.v);
							m--;
						}
					}
				}
			}
		}
		else {
			int x, y;
			cin >> x >> y;
			if (find(x) == find(y)) {
				cout << "Yes" << endl;
			}
			else cout << "No" << endl;
		}
	}
	return 0;
}

提出情報

ジャッジ結果