1308 | 2022-04-18 19:44:37 | k_balint | Játék a síkon | cpp14 | Hibás válasz 0/100 | 20ms | 4408 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';
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 2ms | 2188 KiB | ||||
2 | Hibás válasz | 3ms | 2420 KiB | ||||
subtask2 | 0/9 | ||||||
3 | Hibás válasz | 1ms | 2264 KiB | ||||
4 | Elfogadva | 1ms | 2272 KiB | ||||
subtask3 | 0/10 | ||||||
5 | Elfogadva | 1ms | 2280 KiB | ||||
6 | Elfogadva | 1ms | 2288 KiB | ||||
7 | Elfogadva | 1ms | 2296 KiB | ||||
8 | Hibás válasz | 1ms | 2284 KiB | ||||
9 | Elfogadva | 1ms | 2304 KiB | ||||
10 | Elfogadva | 1ms | 2308 KiB | ||||
11 | Elfogadva | 1ms | 2312 KiB | ||||
12 | Elfogadva | 1ms | 2304 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Elfogadva | 2ms | 2420 KiB | ||||
14 | Hibás válasz | 2ms | 2444 KiB | ||||
15 | Hibás válasz | 2ms | 2560 KiB | ||||
16 | Hibás válasz | 2ms | 2472 KiB | ||||
subtask5 | 0/16 | ||||||
17 | Hibás válasz | 2ms | 2620 KiB | ||||
18 | Hibás válasz | 2ms | 2624 KiB | ||||
19 | Hibás válasz | 2ms | 2500 KiB | ||||
20 | Hibás válasz | 2ms | 2660 KiB | ||||
21 | Elfogadva | 2ms | 2548 KiB | ||||
subtask6 | 0/18 | ||||||
22 | Elfogadva | 2ms | 2532 KiB | ||||
23 | Hibás válasz | 2ms | 2564 KiB | ||||
24 | Hibás válasz | 2ms | 2712 KiB | ||||
25 | Hibás válasz | 2ms | 2588 KiB | ||||
26 | Hibás válasz | 2ms | 2592 KiB | ||||
subtask7 | 0/37 | ||||||
27 | Hibás válasz | 4ms | 3440 KiB | ||||
28 | Elfogadva | 4ms | 3372 KiB | ||||
29 | Hibás válasz | 14ms | 3756 KiB | ||||
30 | Hibás válasz | 20ms | 3984 KiB | ||||
31 | Hibás válasz | 17ms | 3888 KiB | ||||
32 | Hibás válasz | 4ms | 3836 KiB | ||||
33 | Hibás válasz | 4ms | 3284 KiB | ||||
34 | Hibás válasz | 8ms | 3316 KiB | ||||
35 | Elfogadva | 8ms | 3292 KiB | ||||
36 | Hibás válasz | 6ms | 3956 KiB | ||||
37 | Hibás válasz | 7ms | 3984 KiB | ||||
38 | Hibás válasz | 6ms | 4060 KiB | ||||
39 | Hibás válasz | 8ms | 4160 KiB | ||||
40 | Hibás válasz | 8ms | 4236 KiB | ||||
41 | Hibás válasz | 9ms | 4408 KiB | ||||
42 | Hibás válasz | 10ms | 4400 KiB |