結果
| 問題 |
No.2675 KUMA
|
| コンテスト | |
| ユーザー |
 nu50218
|
| 提出日時 | 2024-02-08 17:50:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 10 ms / 2,000 ms |
| コード長 | 13,129 bytes |
| コンパイル時間 | 2,397 ms |
| コンパイル使用メモリ | 148,684 KB |
| 最終ジャッジ日時 | 2025-02-19 02:53:51 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 47 |
ソースコード
// include
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef long long LL;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;
typedef pair<long long, long long> PLL;
typedef vector<pair<ll, ll> > vpll;
// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
// repetition
//------------------------------------------
#define FOR(i, a, b) for (long long i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ENDL cout << endl;
#define CIN(a) REP(i, a.size()) cin >> a[i];
/*
T 型の フロー
diff_ : T 型の a , b に対して、
a ≠ b と abs(a - b) >= diff が同地となるような値
例えば、int なら 1 , double なら 1e-12 とか
(要するに、二分探索の閾値)
*/
template <class T = long long, T diff_ = 1>
struct mxfl {
private:
int edge_id_conuter = 0;
struct edge {
int from, to;
T flow;
int id;
edge(int from, int to, int flow, int id) : from(from), to(to), flow(flow), id(id) {}
edge* r_edge; // 逆辺へのポインタ
};
vector<vector<edge*> > G;
map<pair<int, int>, edge*> edges;
// 何度も bfs するので、reach 配列を使い回したい
int bfs_times = 0; // 何回目の bfs か
vector<pair<int, edge*> > reach; // [x] := first が bfs_times と一致するなら、到達可能で、second が直前に使った辺のポインタ
bool fast_input_mode = false; // 多重辺を許す代わりに、add_edge が速くなる(bfs/dfs は遅くなる)
// 多重辺を許す高速モード
void fast_add_edge(int u, int v, T f) {
edge* e = new edge(u, v, f, ++edge_id_conuter);
edge* r_e = new edge(v, u, 0, ++edge_id_conuter);
(*e).r_edge = r_e;
(*r_e).r_edge = e;
G[u].push_back(e);
G[v].push_back(r_e);
}
vector<edge*> E;
// 静的に add_edge する。その後 build する必要がある。
void static_add_edge(int u, int v, T f) {
edge* e = new edge(u, v, f, ++edge_id_conuter);
edge* re = new edge(v, u, 0, ++edge_id_conuter);
e->r_edge = re;
re->r_edge = e;
E.push_back(e);
E.push_back(re);
}
bool first_commit = false;
// build した後も、 log(E) で 辺を追加できる
void dynamic_add_edge(int u, int v, T f) {
// 最初は statix で追加した辺を map に格納する操作を行う
if (first_commit)
for (int x = 0; x < V; x++)
for (edge* e : G[x]) edges[make_pair(e->from, e->to)] = e;
first_commit = false;
if (edges[make_pair(u, v)] != nullptr) {
(*edges[make_pair(u, v)]).flow += f;
return;
}
edge* e = new edge(u, v, f, ++edge_id_conuter);
edge* r_e = new edge(v, u, 0, ++edge_id_conuter);
(*e).r_edge = r_e;
(*r_e).r_edge = e;
edges[make_pair(u, v)] = e;
edges[make_pair(v, u)] = r_e;
G[u].push_back(e);
G[v].push_back(r_e);
}
public:
int V;
mxfl(int V_, bool fst = false) : V(V_), G(V_), reach(V_, {-1, nullptr}), fast_input_mode(fst) {}
~mxfl() {
for (vector<edge*>& v : G) {
for (int i = int(v.size()) - 1; i >= 0; i--) delete v[i];
}
}
void add_edge(int u, int v, T f) {
if (fast_input_mode)
fast_add_edge(u, v, f); // 多重辺を許す高速モード
else if (!built)
static_add_edge(u, v, f); // build 前は 静的モード
else
dynamic_add_edge(u, v, f); // build 後は 動的モード
}
bool built = false; // build したかどうか
// 静的な add_edge のあとは build 必須
void build() {
if (built || fast_input_mode) return;
built = true;
if (E.size() == 0) return;
sort(E.begin(), E.end(), [&](edge* a, edge* b) {
if (a->from == b->from) {
if (a->to == b->to)
return a->id < b->id; // 宣言のタイミング
else
return a->to < b->to;
} else
return a->from < b->from;
});
// 同じ頂点 (u-v) を結ぶものは、右のものにマージするとよい
// 辺は宣言時に逆編とセットにしており、
// 同じ頂点を結ぶ辺は「宣言順」にソートしており、逆転のポインタとのリンクも保持されたままである
for (int i = 0; i < E.size(); i++) {
if (i + 1 < E.size() && E[i]->from == E[i + 1]->from && E[i]->to == E[i + 1]->to) {
E[i + 1]->flow += E[i]->flow; // 右の辺も同じ頂点を結ぶなら、右にマージ
delete E[i];
} else
G[E[i]->from].push_back(E[i]);
}
E.clear();
}
// s → t の流量 f そのパスを返す , 無理なら first が 0
// パスを返すだけで、何も流さない
pair<bool, vector<edge*> > FindPath(int s, int t, T f) {
bfs_times++;
vector<edge*> path;
if (s == t) return {true, path}; // 未定義動作
queue<int> q;
q.push(s);
bfs_times++;
reach[s] = {bfs_times, nullptr};
while (!q.empty()) {
int now = q.front();
q.pop();
for (edge* e : G[now]) {
if (e->flow >= f) {
if (reach[e->to].first != bfs_times) {
reach[e->to] = {bfs_times, e};
q.push(e->to);
}
}
}
}
if (reach[t].first != bfs_times) return {false, path};
while (t != s) {
path.push_back(reach[t].second);
t = (reach[t].second)->from;
}
reverse(path.begin(), path.end());
return {true, path};
}
// s → t の最大増加道 (パス) の容量を返す(にぶたん)
T CalcMaxPath(int s, int t) {
if (s == t) return 0; //未定義
T left = 0;
T right = 1e9;
while (right - left > diff_) {
T mid = left + (right - left) / 2;
queue<int> q;
q.push(s);
bfs_times++;
reach[s] = {bfs_times, nullptr};
while (!q.empty()) {
int now = q.front();
q.pop();
for (edge* e : G[now]) {
if (e->flow >= mid) {
if (reach[e->to].first != bfs_times) {
reach[e->to] = {bfs_times, e};
q.push(e->to);
}
}
}
}
if (reach[t].first == bfs_times)
left = mid;
else
right = mid;
}
return left;
}
// 実際に s - t パスに f 流す
// 流せないなら、流さない (パスに流すことに注意)
bool Flow(int s, int t, T f) {
auto tmp = FindPath(s, t, f);
if (tmp.first) {
for (edge* e : tmp.second) {
e->flow -= f;
e->r_edge->flow += f;
}
} else {
return false;
}
return true;
}
// s → t に流せるだけ流す
T MaxFlow(int s, int t) {
T res = 0;
while (true) {
bool f = Flow(s, t, 1);
if (!f) break;
res += 1;
}
return res;
}
};
/*
入力で与えられる UMA の座標を +10 ぐらいしておく
座標(index)は (x , y) とする
*/
// [i][j] := (i,j) に 何番目の UMA がいるか (1-index)
// KUMA が置いてあるなら -1 とする
ll grid[2000][2000];
int N;
vector<pair<int, int> > UMA;
// pair(i,j) := i,j を同時に観測する
// ようなペア群 を全て列挙する
vector<vpll> matching;
vpll tmp;
vll tmp2;
void rec(int i, vpll& match_now, vll& memo) {
// i := 何番目の UMA まで調べたか
// match_now := 現在マッチしている UMA のペア
// memo[i] := UMA i がすでに他の UMA とマッチしているか (マッチしている (true) なら無視する)
// (＊＊＊＊＊連結成分 3 以上のマッチは意味がない＊＊＊＊＊)
if (i == N) {
matching.push_back(match_now);
return;
}
rec(i + 1, match_now, memo);
if (memo[i]) return;
memo[i] = 1;
int x = UMA[i].first;
int y = UMA[i].second;
vpll pr = {{x, y + 2}, {x + 2, y}, {x, y - 2}, {x - 2, y}}; // 同時に監視される UMA の座標候補
for (pll pos : pr) {
int id = grid[pos.first][pos.second] - 1;
if (id > i) {
// pos に、自分より番号が大きい UMA がいるなら、マッチングできる
if (memo[id] == 0) {
match_now.emplace_back(i, id);
memo[id] = 1;
rec(i + 1, match_now, memo);
match_now.pop_back();
memo[id] = 0;
}
}
}
memo[i] = 0;
}
const int BORDER = 2000;
int toint(pll p) {
return p.first * BORDER + p.second;
}
pll topair(int id) {
return {id / BORDER, id % BORDER};
}
int COMPRESS[5000000]; // 座標(toint) の座圧結果は毎回書き換えるので、COMPRESS を使い回してOK
int main() {
cin >> N;
UMA.resize(N);
REP(i, N) {
ll x, y;
cin >> x >> y;
x += 20;
y += 20;
UMA[i] = {x, y};
grid[x][y] = i + 1;
}
// 使ったかどうかのメモ用
tmp2.resize(N + 1, 0);
// マッチングを
rec(0, tmp, tmp2);
sort(RALL(matching), [&](vpll& a, vpll& b) { return a.size() < b.size(); });
;
vpll dire = {{-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
for (const vpll& Pairs : matching) {
set<int> Units; //単体の UMA
REP(i, N)
Units.insert(i);
for (pll p : Pairs) {
Units.erase(p.first);
Units.erase(p.second);
}
set<int> A; // このスコープで関係ある座標たちの ID(後で座圧する)
for (pll p : Pairs) {
A.insert(toint(UMA[p.first]));
A.insert(toint(UMA[p.second]));
}
for (ll p : Units) A.insert(toint(UMA[p]));
REP(i, N) {
// 8 方向見る
for (pll nx : dire) {
A.insert(toint(MP(UMA[i].first + nx.first, UMA[i].second + nx.second)));
}
}
int id = 1;
for (ll x : A) COMPRESS[x] = id++; // COMPRESS には 1 ~ |A| がメモされる
// 辺を貼りましょう。
mxfl<int> F(A.size() + Pairs.size() + 2); // A & pair_id & snk & src
int src = 0;
int snk = A.size() + Pairs.size() + 1;
for (int id : A) {
pll p = topair(id);
if (grid[p.first][p.second] >= 1) { // 座標が UMA の場合
F.add_edge(src, COMPRESS[id], 1);
} else {
F.add_edge(COMPRESS[id], snk, 1);
}
}
for (int i : Units) {
// 8 方向見る
for (pll nx : dire) {
ll x = UMA[i].first + nx.first;
ll y = UMA[i].second + nx.second;
if (grid[x][y] >= 1) continue;
F.add_edge(COMPRESS[toint(UMA[i])], COMPRESS[toint(MP(x, y))], 1);
}
}
// ペアの方は、元の UMA の id とは別で id を用意する(これは COMPRESS しなくて OK )
int pair_id = A.size() + 1;
for (pll p : Pairs) {
F.add_edge(src, pair_id, 1);
set<int> KMA_excluded; // ペアの両方の 8 方向をいれていき、重複したものが候補になる
// まずは first から
for (pll nx : dire) {
ll x = UMA[p.first].first + nx.first;
ll y = UMA[p.first].second + nx.second;
KMA_excluded.insert(toint(MP(x, y)));
}
// 次は second
for (pll nx : dire) {
ll x = UMA[p.second].first + nx.first;
ll y = UMA[p.second].second + nx.second;
// 重複 = 候補である
if (KMA_excluded.count(toint(MP(x, y)))) {
if (grid[x][y] >= 1) continue;
F.add_edge(pair_id, COMPRESS[toint(MP(x, y))], 1);
}
}
pair_id++;
}
F.build();
int mxf = F.MaxFlow(src, snk);
if (mxf == N - Pairs.size()) {
cout << mxf << endl;
return 0;
}
}
// 無理だった場合
cout << -1 << endl;
return 0;
}