1307 | 2022-04-18 19:37:35 | k_balint | Játék a síkon | cpp14 | Hibás válasz 0/100 | 41ms | 4304 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};
int 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 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 | 2152 KiB | ||||
2 | Hibás válasz | 3ms | 2376 KiB | ||||
subtask2 | 0/9 | ||||||
3 | Hibás válasz | 1ms | 2200 KiB | ||||
4 | Elfogadva | 1ms | 2208 KiB | ||||
subtask3 | 0/10 | ||||||
5 | Elfogadva | 1ms | 2204 KiB | ||||
6 | Elfogadva | 2ms | 2212 KiB | ||||
7 | Elfogadva | 1ms | 2216 KiB | ||||
8 | Hibás válasz | 1ms | 2224 KiB | ||||
9 | Hibás válasz | 1ms | 2224 KiB | ||||
10 | Hibás válasz | 1ms | 2228 KiB | ||||
11 | Elfogadva | 1ms | 2232 KiB | ||||
12 | Elfogadva | 1ms | 2240 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Elfogadva | 2ms | 2460 KiB | ||||
14 | Hibás válasz | 2ms | 2500 KiB | ||||
15 | Hibás válasz | 2ms | 2520 KiB | ||||
16 | Hibás válasz | 2ms | 2520 KiB | ||||
subtask5 | 0/16 | ||||||
17 | Hibás válasz | 2ms | 2536 KiB | ||||
18 | Hibás válasz | 2ms | 2544 KiB | ||||
19 | Hibás válasz | 2ms | 2556 KiB | ||||
20 | Hibás válasz | 2ms | 2588 KiB | ||||
21 | Elfogadva | 2ms | 2584 KiB | ||||
subtask6 | 0/18 | ||||||
22 | Elfogadva | 2ms | 2576 KiB | ||||
23 | Hibás válasz | 2ms | 2620 KiB | ||||
24 | Hibás válasz | 2ms | 2632 KiB | ||||
25 | Hibás válasz | 2ms | 2628 KiB | ||||
26 | Hibás válasz | 3ms | 2656 KiB | ||||
subtask7 | 0/37 | ||||||
27 | Hibás válasz | 6ms | 3368 KiB | ||||
28 | Elfogadva | 4ms | 3328 KiB | ||||
29 | Hibás válasz | 10ms | 3688 KiB | ||||
30 | Hibás válasz | 41ms | 3728 KiB | ||||
31 | Hibás válasz | 12ms | 3788 KiB | ||||
32 | Hibás válasz | 6ms | 3684 KiB | ||||
33 | Hibás válasz | 7ms | 3180 KiB | ||||
34 | Hibás válasz | 8ms | 3204 KiB | ||||
35 | Hibás válasz | 8ms | 3224 KiB | ||||
36 | Hibás válasz | 6ms | 3808 KiB | ||||
37 | Hibás válasz | 9ms | 3996 KiB | ||||
38 | Hibás válasz | 7ms | 4044 KiB | ||||
39 | Hibás válasz | 13ms | 4128 KiB | ||||
40 | Hibás válasz | 12ms | 4180 KiB | ||||
41 | Hibás válasz | 17ms | 4228 KiB | ||||
42 | Hibás válasz | 20ms | 4304 KiB |