結果
問題 | No.1265 Balloon Survival |
ユーザー |
![]() |
提出日時 | 2020-10-29 20:17:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,168 bytes |
コンパイル時間 | 2,429 ms |
コンパイル使用メモリ | 205,752 KB |
最終ジャッジ日時 | 2025-01-15 16:23:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 WA * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using vec = vector<T>;template <typename T> using vvec = vector<vector<T>>;int main() {int n; cin >> n;vec<array<int, 2>> bal(n);for (auto &[x, y]: bal) cin >> x >> y;using dist_t = array<int, 3>;priority_queue<dist_t, vector<dist_t>, greater<dist_t>> que;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {int ax = bal[i][0], ay = bal[i][1];int bx = bal[j][0], by = bal[j][1];int dx = abs(ax - bx), dy = abs(ay - by);int dist = 0;if (ax == bx || ay == by) {dist = (max(dx, dy) + 1) / 2;}else {dist = (max(dx, dy)) / 2 + 1;}que.push({ dist, i, j });}}int ans = 0;vec<bool> used(n, false);while (que.size()) {auto [d, a, b] = que.top(); que.pop();if (used[a] || used[b]) continue;tie(a, b) = make_tuple(min(a, b), max(a, b));used[a] = a != 0;used[b] = true;ans += a == 0;}cout << ans << endl;}