Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.8 kB
35
Indexable
//Dai Ca Di Hoc
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define For(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define MIN(x,y) if (x > (y)) x = (y)
#define MAX(x,y) if (x < (y)) x = (y)
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define maxn 200005
#define MOD 1000000007
#define remain(x) if (x > MOD) x -= MOD
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vii vector< pii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "mergerect"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;


vector < pll > vcur, vnext;
int n;

pll getpair(ll x, ll y){
    if (x > y) swap(x,y);
    return {x,y};
}

void Update(ll p, ll q){
    if (p > q) swap(p,q);
    pll now = {p,q};
    for (auto x : vnext)
        if (x == now) return;
    vnext.PB(now);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    ll x,y;
    cin >> x >> y;
    vcur.PB(getpair(x,y));
    For(i, 2, n){
        cin >> x >> y;
        if (x > y) swap(x,y);
        for (auto &[p, q] : vcur){
            if (p==x) Update(p, q+y);
            if (p==y) Update(p, q+x);
            if (q==x) Update(q, p+y);
            if (q==y) Update(q, p+x);
        }
        swap(vcur, vnext);
        vnext.clear();
    }
    cout << vcur.size() << "\n";
    for (auto &[p, q] : vcur) cout << p << " " << q << "\n";
    return 0;
}

Leave a Comment