Untitled
unknown
plain_text
a year ago
1.8 kB
45
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;
}
Editor is loading...
Leave a Comment