2802021-06-22 15:26:31mraronJáték a síkoncpp14Elfogadva 100/100326ms4724 KiB
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=3.1415926535897932384626433832795;
const ll INF = 1LL<<62;
const ll MINF = -1LL<<62;

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)

const int MAXN=5001;
int par[MAXN], banned=0;
vector<int> adj[MAXN];
vector<int> comp;
vector<int> color[2];
int st0[MAXN], st1[MAXN];

void dfs0(int x, int c=0) {
    st0[x]=1;
    comp.pb(x);
    color[c].pb(x);
    for(auto i:adj[x]) if(!st0[i]) dfs0(i,c^1);
}

int matching = 0;

bool dfs1(int x) {
    st1[x]=1;
    for(auto i:adj[x]) {
        if(!st1[i] && i!=banned) {
		    if(par[i]==0 || (par[i]!=x && !st1[par[i]] && dfs1(par[i]))) {
				if(par[i]==0) matching++;

				par[x]=i;
				par[i]=x;
                return true;
            }
        }
    }
    return false;
}

int match(bool early=false) {
    bool done_smth;
    do {
        for(int i:comp) {
            st1[i]=0;
        }
    
        done_smth=false;
        for(int i:color[0]) {
            if(i!=banned && !st1[i] && par[i]==0) {
                done_smth|=dfs1(i);
				if(done_smth && early) break ;
            }
        }
    }while(done_smth);
        
    return matching;
}

vector<int> answer(int ind) {
    if(st0[ind]) return {};
    color[0].clear();
    color[1].clear();

    comp.clear();

    dfs0(ind);
	if(sz(color[0])>sz(color[1])) color[0].swap(color[1]);

    for(int i:comp) {
        par[i]=0;
    }
    
    int max_matching=match();
    vector<int> ans;

    for(int i:comp) {
        banned=i;
        
        if(par[banned]) {
            par[par[banned]]=0;
            par[banned]=0;
			matching--;
        }

        int matching=match(true);
        if(matching==max_matching) ans.pb(i);
    }
    
    return ans;
}

int main() {
	IO;
    int n;
    cin>>n;
    vector<pair<int,int>> t(n);
    map<pair<int,int>, int> conv;
    for(int i=0;i<n;++i) {
        cin>>t[i].xx>>t[i].yy;
        conv[t[i]]=i+1;
    }
    
    for(int i=0;i<n;++i) {
        pair<int,int> pt1={t[i].xx+1, t[i].yy};
        pair<int,int> pt2={t[i].xx, t[i].yy+1};
        if(conv.count(pt1)) {
            adj[conv[pt1]].pb(i+1);
            adj[i+1].pb(conv[pt1]);
        }

        if(conv.count(pt2)) {
            adj[conv[pt2]].pb(i+1);
            adj[i+1].pb(conv[pt2]);
        }
    }
    
    vector<int> ans;
    for(int i=1;i<=n;++i) {
        for(auto j:answer(i)) ans.pb(j);
    }
    
    cout<<sz(ans)<<"\n";
    for(auto i:ans) cout<<t[i-1].xx<<" "<<t[i-1].yy<<"\n";
    
	return 0;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms2012 KiB
2Elfogadva8ms2460 KiB
subtask29/9
3Elfogadva2ms2108 KiB
4Elfogadva1ms2112 KiB
subtask310/10
5Elfogadva1ms2116 KiB
6Elfogadva1ms2120 KiB
7Elfogadva1ms2132 KiB
8Elfogadva1ms2132 KiB
9Elfogadva1ms2140 KiB
10Elfogadva2ms2140 KiB
11Elfogadva1ms2144 KiB
12Elfogadva1ms2152 KiB
subtask410/10
13Elfogadva2ms2376 KiB
14Elfogadva2ms2424 KiB
15Elfogadva2ms2432 KiB
16Elfogadva3ms2460 KiB
subtask516/16
17Elfogadva8ms2500 KiB
18Elfogadva8ms2496 KiB
19Elfogadva7ms2496 KiB
20Elfogadva8ms2512 KiB
21Elfogadva8ms2568 KiB
subtask618/18
22Elfogadva2ms2500 KiB
23Elfogadva2ms2536 KiB
24Elfogadva2ms2548 KiB
25Elfogadva2ms2552 KiB
26Elfogadva4ms2588 KiB
subtask737/37
27Elfogadva4ms3332 KiB
28Elfogadva4ms3340 KiB
29Elfogadva149ms4044 KiB
30Elfogadva104ms4264 KiB
31Elfogadva129ms4280 KiB
32Elfogadva7ms3776 KiB
33Elfogadva13ms3344 KiB
34Elfogadva14ms3384 KiB
35Elfogadva10ms3408 KiB
36Elfogadva7ms3900 KiB
37Elfogadva13ms4004 KiB
38Elfogadva8ms3992 KiB
39Elfogadva188ms4548 KiB
40Elfogadva259ms4592 KiB
41Elfogadva86ms4724 KiB
42Elfogadva326ms4636 KiB