Submission

Score: 58

User: pxsit

Problemset: Tech Sprites

Language: cpp

Time: 2.613 second

Submitted On: 2025-07-23 21:36:36

#include <bits/stdc++.h>
using namespace std;
int par[1000005];
int findpar(int u){
    return (u == par[u] ? u : par[u] = findpar(par[u]));
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<pair<int,int>> tech(n+1);
    vector<vector<pair<int,int>>> cycle(n+1);
    for(int i=1;i<=n;i++){
        par[i] = i;
        int a,b;
        cin >> a >> b;
        tech[i].first = a;
        tech[i].second = b;
        cycle[i].emplace_back(a,b);
    }
    for(int j=0;j<m;j++){
        int u,v;
        cin >> u >> v;
        if(u>v) swap(u,v);
        int pu = findpar(u);
        int pv = findpar(v);
        if(pu != pv){
            // cout << "WE swap PU AND PV AND U AND V " << pu << ' ' << pv << ' ' << u << ' ' << v << '\n';
            par[pu] = pv;
            // cycle[pv] += cycle[pu];
            for(auto i : cycle[pu]) cycle[pv].emplace_back(i);
            // cycle[pv].emplace_back(tech[pu]);
            // cout << "CYC ST\n"; 
            // for(auto i : cycle[pv]) cout << "Cycle "  << i.first << ' ' << i.second << '\n'; 
            // cout << "CYC ND\n"; 
            cycle[pu].clear();
        }
    }
    for(int i=1;i<=n;i++){
        sort(cycle[i].begin(),cycle[i].end());
    }
    vector<pair<pair<int,int>,pair<int,int>>> mp;
    // sort(cycle.begin(),cycle.end());
    // cout << 1;
    for(int i=1;i<=n;i++){
        if(cycle[i].empty()) continue;
        pair<int,int> mn = {0x3f3f3f3f,0x3f3f3f3f},mx = {-1,-1};
        for(auto j : cycle[i]){
            if(j.first < mn.first){
                mn = j;
            }else if(j.first == mn.first){
                if(j.second < mn.second) mn = j;
            }
            if(j.first > mx.first){
                mx = j;
            }else if(j.first == mx.first){
                if(j.second > mx.second) mx = j;
            }
            // cout << "Cycle " << i << " is " << j.first << ' ' << j.second << '\n';
        }
        // if(mx.first == -1) continue;
        mp.emplace_back(mn,mx);
    }
    sort(mp.begin(),mp.end());
    int ans = 0;
    for(int i=1;i<mp.size();i++){
        if(mp[i].first.first < mp[i-1].second.first){
            ans++;
            if(mp[i-1].second.first > mp[i].second.first) mp[i].second = mp[i-1].second;
            if(mp[i].second.first == mp[i-1].second.first) mp[i].second.second = max(mp[i].second.second,mp[i-1].second.second);
        }else if(mp[i].first.first == mp[i-1].second.first){
            if(mp[i].first.second < mp[i-1].second.second){
                ans++;
                if(mp[i-1].second.first > mp[i].second.first) mp[i].second = mp[i-1].second;
                if(mp[i].second.first == mp[i-1].second.first) mp[i].second.second = max(mp[i].second.second,mp[i-1].second.second);
            }
        }
        // cout << mp[i].first.first << ' ' << mp[i].first.second << ' ' << mp[i].second.first << ' ' << mp[i].second.second << '\n';
    }
    cout << ans;
}