제출 #1080773

#제출 시각아이디문제언어결과실행 시간메모리
1080773asdasdqwer봉쇄 시간 (IOI23_closing)C++17
8 / 100
90 ms40020 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii array<int,2> #define pll array<ll, 2> ll BIG = 1e18+1; int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<vector<pll>> g(N); for (int i=0;i<N-1;i++) { g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); } function<void(int, vector<ll>&)> dfs=[&](int node, vector<ll> &dis) { for (auto [ne, we]:g[node]) { if (dis[ne] != -1) continue; dis[ne] = dis[node] + we; dfs(ne, dis); } }; vector<ll> disx(N, -1), disy(N, -1); disx[X] = 0;disy[Y]=0; dfs(X, disx);dfs(Y, disy); vector<ll> c(N, 0); ll sm = 0; vector<bool> visx(N, false), visy(N, false); vector<pll> sx, sy; visx[X]=true;visy[Y]=true; for (auto [ne, we] : g[X]) { visx[ne]=true; sx.push_back({we, ne}); } for (auto [ne, we] : g[Y]) { visy[ne]=true; sy.push_back({we, ne}); } int reach = 2; while (sm < K && sx.size() + sy.size() != 0) { // get minimum contribution sort(sx.begin(), sx.end()); sort(sy.begin(), sy.end()); pll mn = {BIG, BIG}; if (sx.size()) mn = min(mn, sx[0]); if (sy.size()) mn = min(mn, sy[0]); if (mn[0] + sm > K) break; // cout << mn[1] << endl; if (sx.size() && mn == sx[0]) { auto [we, node] = mn; sm += we; c[node] += we; reach++; sx.erase(sx.begin()); // first check for other for (auto &x:sy) { if (x[1] == node) { x[0] = x[0] - c[node]; } } for (auto [ne, we2] : g[node]) { if (visx[ne]) continue; visx[ne]=true; sx.push_back({we+we2-c[ne], ne}); } } else { auto [we, node] = mn; sm += we; c[node] += we; reach++; sy.erase(sy.begin()); // first check for other for (auto &x:sx) { if (x[1] == node) { x[0] = x[0] - c[node]; } } for (auto [ne, we2] : g[node]) { if (visy[ne]) continue; visy[ne]=true; sy.push_back({we+we2-c[ne], ne}); } } } // for (auto &x:c) cout << x << " "; // cout<<endl; return reach; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...