1309 | 2022-04-18 19:47:08 | k_balint | Játék a síkon | cpp14 | Accepted 100/100 | 18ms | 4300 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=5005;
int n,tt;
vector<int> adj[c];
int vis[c],par[c];
bool A[c],ans[c];
map<pair<int,int>,int> m;
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
pair<int,int> arr[c];
bool novel(int v){
if(vis[v]==tt) return 0;
vis[v]=tt;
for(int x:adj[v]){
if(vis[x]==tt) continue;
if(par[x]==x){
par[v]=x; par[x]=v;
return 1;
}
else{
vis[x]=tt;
if(novel(par[x])){
par[v]=x; par[x]=v;
return 1;
}
}
}
return 0;
}
void magyar(){
for(int i=1;i<=n;i++) par[i]=i;
tt=1;
for(int i=1;i<=n;i++){
if(A[i] && par[i]==i){
++tt; novel(i);
}
}
}
void edg(int i){
for(int j=0;j<4;j++){
int nx=arr[i].first+xx[j]; int ny=arr[i].second+yy[j];
auto it=m.find(make_pair(nx,ny));
if(it!=m.end()){
adj[i].push_back(it->second);
adj[it->second].push_back(i);
}
}
}
void dfsa(int v){
vis[v]=tt;
if(A[v]) ans[v]=1;
for(int x:adj[v]){
if(vis[x]==tt) continue;
if((A[v] && par[v] != x) || (!A[v] && par[v]==x)) dfsa(x);
}
}
void dfsb(int v){
vis[v]=tt;
if(!A[v]) ans[v]=1;
for(int x:adj[v]){
if(vis[x]==tt) continue;
if((!A[v]&&par[v]!=x)|| (A[v]&&par[v]==x)) dfsb(x);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int a,b; cin>>a>>b;
arr[i]=make_pair(a,b);
m[arr[i]]=i; edg(i);
A[i]=(a+b)&1;
}
magyar();
for(int i=1;i<=n;i++){
if(par[i]==i){
++tt;
if(A[i]) dfsa(i);
else dfsb(i);
}
}
int cnt=0;
for(int i=1;i<=n;i++) {
if(ans[i]) ++cnt;
}
cout << cnt << '\n';
for(int i=1;i<=n;i++){
if(ans[i]) cout << arr[i].first << ' ' << arr[i].second << '\n';
}
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 2ms | 2148 KiB | ||||
2 | Accepted | 3ms | 2380 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Accepted | 1ms | 2224 KiB | ||||
4 | Accepted | 1ms | 2236 KiB | ||||
subtask3 | 10/10 | ||||||
5 | Accepted | 1ms | 2244 KiB | ||||
6 | Accepted | 1ms | 2248 KiB | ||||
7 | Accepted | 1ms | 2256 KiB | ||||
8 | Accepted | 1ms | 2252 KiB | ||||
9 | Accepted | 1ms | 2248 KiB | ||||
10 | Accepted | 1ms | 2260 KiB | ||||
11 | Accepted | 1ms | 2264 KiB | ||||
12 | Accepted | 1ms | 2268 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Accepted | 2ms | 2380 KiB | ||||
14 | Accepted | 2ms | 2400 KiB | ||||
15 | Accepted | 2ms | 2420 KiB | ||||
16 | Accepted | 2ms | 2572 KiB | ||||
subtask5 | 16/16 | ||||||
17 | Accepted | 2ms | 2572 KiB | ||||
18 | Accepted | 2ms | 2576 KiB | ||||
19 | Accepted | 2ms | 2592 KiB | ||||
20 | Accepted | 2ms | 2620 KiB | ||||
21 | Accepted | 2ms | 2500 KiB | ||||
subtask6 | 18/18 | ||||||
22 | Accepted | 2ms | 2492 KiB | ||||
23 | Accepted | 2ms | 2516 KiB | ||||
24 | Accepted | 2ms | 2664 KiB | ||||
25 | Accepted | 2ms | 2672 KiB | ||||
26 | Accepted | 2ms | 2688 KiB | ||||
subtask7 | 37/37 | ||||||
27 | Accepted | 4ms | 3400 KiB | ||||
28 | Accepted | 4ms | 3344 KiB | ||||
29 | Accepted | 14ms | 3704 KiB | ||||
30 | Accepted | 18ms | 3792 KiB | ||||
31 | Accepted | 16ms | 3860 KiB | ||||
32 | Accepted | 4ms | 3788 KiB | ||||
33 | Accepted | 4ms | 3256 KiB | ||||
34 | Accepted | 8ms | 3280 KiB | ||||
35 | Accepted | 8ms | 3272 KiB | ||||
36 | Accepted | 6ms | 3936 KiB | ||||
37 | Accepted | 8ms | 4000 KiB | ||||
38 | Accepted | 6ms | 4072 KiB | ||||
39 | Accepted | 8ms | 4172 KiB | ||||
40 | Accepted | 8ms | 4188 KiB | ||||
41 | Accepted | 8ms | 4284 KiB | ||||
42 | Accepted | 12ms | 4300 KiB |