結果
問題 | No.1898 Battle and Exchange |
ユーザー |
👑 ![]() |
提出日時 | 2022-04-08 22:19:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 600 ms / 5,000 ms |
コード長 | 2,545 bytes |
コンパイル時間 | 1,106 ms |
コンパイル使用メモリ | 91,508 KB |
最終ジャッジ日時 | 2025-01-28 16:17:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 58 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <queue>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)int N,M;vector<vector<int>> E;vector<array<i64, 3>> A;i64 sum(array<i64, 3> a){i64 ans = 0;for(auto aa : a) ans += aa;return ans;}bool battle(array<i64, 3>& a, array<i64, 3> b){if(sum(a) <= sum(b)) return false;if(a[0] < b[2]) swap(a[0], b[2]);return true;}bool battle2(array<i64, 3>& a, array<i64, 3> b){if(sum(a) <= sum(b)) return false;array<i64, 6> buf;rep(t,3) buf[t] = a[t];rep(t,3) buf[3+t] = b[t];sort(buf.begin(), buf.end());rep(t,3) a[t] = buf[3+t];return true;}bool solve(array<i64, 3> P){auto p = P;if(!battle(p, A[0])) return false;bool ok = false;for(auto e : E[0]) if(battle(p, A[e])) ok = true;if(!ok) return false;p = P;vector<int> pushed(N, 0);vector<int> vis(N, 0);priority_queue<pair<i64, int>> Q;Q.push(make_pair(-sum(A[0]), 0));pushed[0] = 1;//cout << " P = [ " << P[0] << ", " << P[1] << ", " << P[2] << " ]" << endl;while(Q.size()){int v = Q.top().second;Q.pop();if(!battle2(p, A[v])) break;//cout << " v = " << v << ", p = [ " << p[0] << ", " << p[1] << ", " << p[2] << " ]" << endl;vis[v] = 1;for(int e : E[v]) if(!pushed[e]){Q.push(make_pair(-sum(A[e]), e));pushed[e] = 1;}}return vis[N-1];}int main(){cin >> N >> M;E.resize(N);rep(i,M){int u,v; cin >> u >> v; u--; v--;E[u].push_back(v);E[v].push_back(u);}A.resize(N);rep(i,N) rep(t,3){ cin >> A[i][t]; A[i][t]--; }rep(i,N) sort(A[i].begin(), A[i].end());array<i64,3> ans;rep(t,3) ans[t] = 1<<30;{i64 ng = 0, ok = 1<<30;while(ng + 1 < ok){i64 m = (ng+ok) / 2;array<i64, 3> init = {};init[2] = m;if(solve(init)) ok = m; else ng = m;}array<i64, 3> tmp = {};tmp[2] = ok;if(sum(ans) > sum(tmp)) ans = tmp;}rep(t,3){if(t) cout << ' ';cout << (ans[t] + 1);}cout << '\n';return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;