13072022-04-18 19:37:35k_balintJáték a síkoncpp14Hibás válasz 0/10041ms4304 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms2152 KiB
2Hibás válasz3ms2376 KiB
subtask20/9
3Hibás válasz1ms2200 KiB
4Elfogadva1ms2208 KiB
subtask30/10
5Elfogadva1ms2204 KiB
6Elfogadva2ms2212 KiB
7Elfogadva1ms2216 KiB
8Hibás válasz1ms2224 KiB
9Hibás válasz1ms2224 KiB
10Hibás válasz1ms2228 KiB
11Elfogadva1ms2232 KiB
12Elfogadva1ms2240 KiB
subtask40/10
13Elfogadva2ms2460 KiB
14Hibás válasz2ms2500 KiB
15Hibás válasz2ms2520 KiB
16Hibás válasz2ms2520 KiB
subtask50/16
17Hibás válasz2ms2536 KiB
18Hibás válasz2ms2544 KiB
19Hibás válasz2ms2556 KiB
20Hibás válasz2ms2588 KiB
21Elfogadva2ms2584 KiB
subtask60/18
22Elfogadva2ms2576 KiB
23Hibás válasz2ms2620 KiB
24Hibás válasz2ms2632 KiB
25Hibás válasz2ms2628 KiB
26Hibás válasz3ms2656 KiB
subtask70/37
27Hibás válasz6ms3368 KiB
28Elfogadva4ms3328 KiB
29Hibás válasz10ms3688 KiB
30Hibás válasz41ms3728 KiB
31Hibás válasz12ms3788 KiB
32Hibás válasz6ms3684 KiB
33Hibás válasz7ms3180 KiB
34Hibás válasz8ms3204 KiB
35Hibás válasz8ms3224 KiB
36Hibás válasz6ms3808 KiB
37Hibás válasz9ms3996 KiB
38Hibás válasz7ms4044 KiB
39Hibás válasz13ms4128 KiB
40Hibás válasz12ms4180 KiB
41Hibás válasz17ms4228 KiB
42Hibás válasz20ms4304 KiB