280 2021. 06. 22 15:26:31 mraron Játék a síkon cpp14 Elfogadva 100/100 326ms 4724 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 2012 KiB
2 Elfogadva 8ms 2460 KiB
subtask2 9/9
3 Elfogadva 2ms 2108 KiB
4 Elfogadva 1ms 2112 KiB
subtask3 10/10
5 Elfogadva 1ms 2116 KiB
6 Elfogadva 1ms 2120 KiB
7 Elfogadva 1ms 2132 KiB
8 Elfogadva 1ms 2132 KiB
9 Elfogadva 1ms 2140 KiB
10 Elfogadva 2ms 2140 KiB
11 Elfogadva 1ms 2144 KiB
12 Elfogadva 1ms 2152 KiB
subtask4 10/10
13 Elfogadva 2ms 2376 KiB
14 Elfogadva 2ms 2424 KiB
15 Elfogadva 2ms 2432 KiB
16 Elfogadva 3ms 2460 KiB
subtask5 16/16
17 Elfogadva 8ms 2500 KiB
18 Elfogadva 8ms 2496 KiB
19 Elfogadva 7ms 2496 KiB
20 Elfogadva 8ms 2512 KiB
21 Elfogadva 8ms 2568 KiB
subtask6 18/18
22 Elfogadva 2ms 2500 KiB
23 Elfogadva 2ms 2536 KiB
24 Elfogadva 2ms 2548 KiB
25 Elfogadva 2ms 2552 KiB
26 Elfogadva 4ms 2588 KiB
subtask7 37/37
27 Elfogadva 4ms 3332 KiB
28 Elfogadva 4ms 3340 KiB
29 Elfogadva 149ms 4044 KiB
30 Elfogadva 104ms 4264 KiB
31 Elfogadva 129ms 4280 KiB
32 Elfogadva 7ms 3776 KiB
33 Elfogadva 13ms 3344 KiB
34 Elfogadva 14ms 3384 KiB
35 Elfogadva 10ms 3408 KiB
36 Elfogadva 7ms 3900 KiB
37 Elfogadva 13ms 4004 KiB
38 Elfogadva 8ms 3992 KiB
39 Elfogadva 188ms 4548 KiB
40 Elfogadva 259ms 4592 KiB
41 Elfogadva 86ms 4724 KiB
42 Elfogadva 326ms 4636 KiB