Submission
Status:
(-SSSSS)(-SSSSS)(-SSSSS)(-SSSSSSS)(-SSSSS)(-SSSSSSSSSSSS)
Subtask/Task Score:
{0/13}{0/11}{0/10}{0/16}{0/18}{0/32}
Score: 0
User: KantaponZ
Problemset: Tech Sprites
Language: cpp
Time: 1.440 second
Submitted On: 2025-06-11 12:20:08
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<tuple<int,int,int>> v;
vector<int> order(1000002), num(1000001);
int pa[1000001];
int fp(int n) {
if (pa[n] == n) {
return n;
}
return pa[n] = fp(pa[n]);
}
int main() {
ios_base::sync_with_stdio(), cin.tie(0);
cin >> n >> m;
if (n == 1) {
cout << 0;
return 0;
}
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
v.push_back({a,b,i});
pa[i] = i;
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++) {
auto [a, b, x] = v[i-1];
order[i] = x;
//cout << x << " ";
}
//cout << endl;
while (m--) {
int u, v;
cin >> u >> v;
int pu = fp(u), pv = fp(v);
if (pu != pv) {
pa[pu] = pv;
}
}
for (int i = 1; i <= n; i++) {
num[fp(i)]++;
}
num[fp(order[1])]--;
//cout << num[fp(order[0])] << endl;
int ct = 0;
for (int a = 2; a <= n; a++) {
int x = order[a - 1];
int i = order[a];
int px = fp(x), pi = fp(i);
if (px == pi) {
num[pi]--;
continue;
}
if (num[px] <= 0) {
num[pi]--;
continue;
}
if (px != pi && num[px] > 0) {
pa[pi] = px;
num[px] += num[pi] - 1;
num[pi] = 0;
ct++;
cout << x << " " << i << endl;
}
}
cout << ct;
}