1304 2022. 04. 14 22:06:18 Valaki2 Játék a síkon cpp14 Elfogadva 100/100 59ms 3884 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int n;
vector<pair<int, int> > coords;
vector<vector<int> > g;
vector<bool> A;
vector<bool> B;
vector<bool> vis;
vector<int> pr;
vector<bool> win;

void get_parties(int cur, bool which) {
    if(which) {
        A[cur] = true;
    } else {
        B[cur] = true;
    }
    vis[cur] = true;
    for(int nei : g[cur]) {
        if(!vis[nei]) {
            get_parties(nei, !which);
        }
    }
}

bool dfs(int a) {
    if(vis[a]) {
        return false;
    }
    vis[a] = true;
    for(int b : g[a]) {
        if(pr[b] == -1 || dfs(pr[b])) {
            pr[b] = a;
            pr[a] = b;
            return true;
        }
    }
    return false;
}

void win_a(int cur) {
    if(vis[cur]) {
        return;
    }
    vis[cur] = true;
    if(A[cur]) {
        win[cur] = true;
    }
    for(int nei : g[cur]) {
        if((A[cur] && pr[cur] != nei) || (B[cur] && pr[cur] == nei)) {
            win_a(nei);
        }
    }
}

void win_b(int cur) {
    if(vis[cur]) {
        return;
    }
    vis[cur] = true;
    if(B[cur]) {
        win[cur] = true;
    }
    for(int nei : g[cur]) {
        if((B[cur] && pr[cur] != nei) || (A[cur] && pr[cur] == nei)) {
            win_b(nei);
        }
    }
}

void solve() {
    cin >> n;
    coords.assign(1 + n, mp(0, 0));
    for(int i = 1; i <= n; i++) {
        cin >> coords[i].fi >> coords[i].se;
    }
    g.resize(1 + n);
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(abs(coords[i].fi - coords[j].fi) + abs(coords[i].se - coords[j].se) == 1) {
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    A.assign(1 + n, false);
    B.assign(1 + n, false);
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            get_parties(i, 0);
        }
    }
    pr.assign(1 + n, -1);
    for(int i = 1; i <= n; i++) {
        if(A[i]) {
            vis.assign(1 + n, false);
            dfs(i);
        }
    }
    win.assign(1 + n, false);
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(A[i] && pr[i] == -1) {
            win_a(i);
        }
    }
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(B[i] && pr[i] == -1) {
            win_b(i);
        }
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(win[i]) {
            ans.pb(i);
        }
    }
    cout << (int) ans.size() << "\n";
    for(int cur : ans) {
        cout << coords[cur].fi << " " << coords[cur].se << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1816 KiB
2 Elfogadva 4ms 2028 KiB
subtask2 9/9
3 Elfogadva 1ms 1868 KiB
4 Elfogadva 1ms 1868 KiB
subtask3 10/10
5 Elfogadva 1ms 1880 KiB
6 Elfogadva 1ms 1876 KiB
7 Elfogadva 1ms 1880 KiB
8 Elfogadva 1ms 1884 KiB
9 Elfogadva 1ms 1892 KiB
10 Elfogadva 1ms 1900 KiB
11 Elfogadva 1ms 1900 KiB
12 Elfogadva 1ms 1900 KiB
subtask4 10/10
13 Elfogadva 3ms 1964 KiB
14 Elfogadva 4ms 2008 KiB
15 Elfogadva 3ms 2012 KiB
16 Elfogadva 3ms 2032 KiB
subtask5 16/16
17 Elfogadva 3ms 2188 KiB
18 Elfogadva 3ms 2060 KiB
19 Elfogadva 4ms 2068 KiB
20 Elfogadva 3ms 2080 KiB
21 Elfogadva 3ms 2256 KiB
subtask6 18/18
22 Elfogadva 3ms 2080 KiB
23 Elfogadva 4ms 2120 KiB
24 Elfogadva 3ms 2124 KiB
25 Elfogadva 4ms 2140 KiB
26 Elfogadva 4ms 2168 KiB
subtask7 37/37
27 Elfogadva 45ms 2616 KiB
28 Elfogadva 46ms 2620 KiB
29 Elfogadva 48ms 3184 KiB
30 Elfogadva 59ms 3292 KiB
31 Elfogadva 59ms 3336 KiB
32 Elfogadva 46ms 3048 KiB
33 Elfogadva 12ms 2840 KiB
34 Elfogadva 10ms 2872 KiB
35 Elfogadva 9ms 2880 KiB
36 Elfogadva 46ms 3236 KiB
37 Elfogadva 48ms 3264 KiB
38 Elfogadva 46ms 3264 KiB
39 Elfogadva 52ms 3600 KiB
40 Elfogadva 56ms 3688 KiB
41 Elfogadva 59ms 3884 KiB
42 Elfogadva 52ms 3772 KiB