13082022-04-18 19:44:37k_balintJáték a síkoncpp14Hibás válasz 0/10020ms4408 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms2188 KiB
2Hibás válasz3ms2420 KiB
subtask20/9
3Hibás válasz1ms2264 KiB
4Elfogadva1ms2272 KiB
subtask30/10
5Elfogadva1ms2280 KiB
6Elfogadva1ms2288 KiB
7Elfogadva1ms2296 KiB
8Hibás válasz1ms2284 KiB
9Elfogadva1ms2304 KiB
10Elfogadva1ms2308 KiB
11Elfogadva1ms2312 KiB
12Elfogadva1ms2304 KiB
subtask40/10
13Elfogadva2ms2420 KiB
14Hibás válasz2ms2444 KiB
15Hibás válasz2ms2560 KiB
16Hibás válasz2ms2472 KiB
subtask50/16
17Hibás válasz2ms2620 KiB
18Hibás válasz2ms2624 KiB
19Hibás válasz2ms2500 KiB
20Hibás válasz2ms2660 KiB
21Elfogadva2ms2548 KiB
subtask60/18
22Elfogadva2ms2532 KiB
23Hibás válasz2ms2564 KiB
24Hibás válasz2ms2712 KiB
25Hibás válasz2ms2588 KiB
26Hibás válasz2ms2592 KiB
subtask70/37
27Hibás válasz4ms3440 KiB
28Elfogadva4ms3372 KiB
29Hibás válasz14ms3756 KiB
30Hibás válasz20ms3984 KiB
31Hibás válasz17ms3888 KiB
32Hibás válasz4ms3836 KiB
33Hibás válasz4ms3284 KiB
34Hibás válasz8ms3316 KiB
35Elfogadva8ms3292 KiB
36Hibás válasz6ms3956 KiB
37Hibás válasz7ms3984 KiB
38Hibás válasz6ms4060 KiB
39Hibás válasz8ms4160 KiB
40Hibás válasz8ms4236 KiB
41Hibás válasz9ms4408 KiB
42Hibás válasz10ms4400 KiB