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 |