結果
問題 | No.1265 Balloon Survival |
ユーザー |
![]() |
提出日時 | 2020-10-29 18:57:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 876 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 205,692 KB |
最終ジャッジ日時 | 2025-01-15 16:22:38 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 WA * 18 |
ソースコード
#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) {que.push({ (max(abs(bal[i][0] - bal[j][0]), abs(bal[i][1] - bal[j][1])) + 1) / 2, 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;}