Submission #1171437

#TimeUsernameProblemLanguageResultExecution timeMemory
1171437anmattroiClosing Time (IOI23_closing)C++17
100 / 100
295 ms55224 KiB
#include "closing.h" #include <bits/stdc++.h> #define maxn 200005 #define fi first #define se second using namespace std; using ii = pair<int, int>; using li = pair<int64_t, int>; int n, x, y; int64_t k; int64_t disX[maxn], disY[maxn]; int64_t cost_level_one[maxn], cost_level_two[maxn]; vector<ii> adj[maxn]; void calcdisX() { function<void(int, int)> dfs = [&](int u, int dad) { for (auto [v, l] : adj[u]) if (v != dad) { disX[v] = disX[u] + l; dfs(v, u); } }; disX[x] = 0; dfs(x, -1); } void calcdisY() { function<void(int, int)> dfs = [&](int u, int dad) { for (auto [v, l] : adj[u]) if (v != dad) { disY[v] = disY[u] + l; dfs(v, u); } }; disY[y] = 0; dfs(y, -1); } int sub1() { vector<int64_t> nho; for (int i = 0; i < n; i++) nho.emplace_back(min(disX[i], disY[i])); sort(nho.begin(), nho.end()); int64_t ans = 0; for (int i = 0; i < n; i++) { ans += nho[i]; if (ans > k) return i; } return n; } int sub2() { int ans = 0; for (int i = 0; i < n; i++) { cost_level_one[i] = min(disX[i], disY[i]); cost_level_two[i] = max(disX[i], disY[i]) - cost_level_one[i]; } int64_t sum = 0; multiset<li> q1, q2, q3; for (int i = 0; i < n; i++) if (disX[i] + disY[i] == disX[y]) { ++ans; sum += cost_level_one[i]; q1.insert({cost_level_two[i], i}); } else { if (cost_level_one[i] > cost_level_two[i]) { q2.insert({cost_level_one[i] + cost_level_two[i], i}); q3.insert({cost_level_one[i], i}); } else { q1.insert({cost_level_one[i], i}); q1.insert({cost_level_two[i], i}); } } if (sum > k) return 0; while (1) { if (q1.empty() and q2.empty()) break; if (sum + (q1.empty() ? LLONG_MAX/4 : q1.begin()->fi) > k and sum + (q2.empty() ? LLONG_MAX/4 : q2.begin()->fi) > k) { if (sum + (q3.empty() ? LLONG_MAX/4 : q3.begin()->fi) > k) break; sum += q3.begin()->fi; ++ans; break; } if (q1.size() >= 2 && !q2.empty()) { int64_t s1 = q1.begin()->fi + next(q1.begin())->fi; if (s1 < q2.begin()->fi) { if (sum + q1.begin()->fi > k) { if (sum + q3.begin()->fi <= k) { sum += q3.begin()->fi; ++ans; } break; } sum += q1.begin()->fi; ++ans; q1.erase(q1.begin()); continue; } if (sum + q2.begin()->fi > k) { if (sum + q1.begin()->fi + q3.begin()->fi <= k) { ans += 2; break; } else if (sum + min(q1.begin()->fi, q3.begin()->fi) <= k) { ++ans; break; } break; } sum += q2.begin()->fi; ans += 2; q3.erase(li{cost_level_one[q2.begin()->se], q2.begin()->se}); q2.erase(q2.begin()); continue; } if (q2.empty()) { if (sum + q1.begin()->fi > k) break; sum += q1.begin()->fi; ++ans; q1.erase(q1.begin()); continue; } if (sum + q2.begin()->fi > k) { if (q1.empty()) { if (sum + q3.begin()->fi <= k) ++ans; break; } if (sum + q1.begin()->fi + q3.begin()->fi <= k) { ans += 2; break; } else if (sum + min(q1.begin()->fi, q3.begin()->fi) <= k) { ++ans; break; } break; } sum += q2.begin()->fi; ans += 2; q3.erase(li{cost_level_one[q2.begin()->se], q2.begin()->se}); q2.erase(q2.begin()); } return ans; } /* 1 5 2 3 91 1 0 25 2 1 16 3 2 71 4 3 62 //34 + 49 4 */ int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { n = N; x = X; y = Y; k = K; for (int i = 0; i < N-1; i++) { adj[U[i]].emplace_back(V[i], W[i]); adj[V[i]].emplace_back(U[i], W[i]); } calcdisX(); calcdisY(); int ans = max(sub1(), sub2()); for (int i = 0; i < N; i++) adj[i].clear(); return ans; } //namespace sub_trau { // // // int n, x, y; int64_t k; // // int64_t dp[3005][6005]; // int64_t disX[3005], disY[3005]; // // int64_t cost_level_one[3005], cost_level_two[3005]; // // vector<ii> adj[3005]; // // void calcdisX() { // // function<void(int, int)> dfs = [&](int u, int dad) { // for (auto [v, l] : adj[u]) // if (v != dad) { // disX[v] = disX[u] + l; // dfs(v, u); // } // }; // // disX[x] = 0; // dfs(x, -1); // } // // void calcdisY() { // // function<void(int, int)> dfs = [&](int u, int dad) { // for (auto [v, l] : adj[u]) // if (v != dad) { // disY[v] = disY[u] + l; // dfs(v, u); // } // }; // // disY[y] = 0; // dfs(y, -1); // } // // // int sub1() { // vector<int64_t> nho; // for (int i = 0; i < n; i++) nho.emplace_back(min(disX[i], disY[i])); // sort(nho.begin(), nho.end()); // // int64_t ans = 0; // for (int i = 0; i < n; i++) { // ans += nho[i]; // if (ans > k) return i; // } // return n; // } // // // int sub2() { // for (int i = 0; i < n; i++) { // cost_level_two[i] = max(disX[i], disY[i]); // cost_level_one[i] = min(disX[i], disY[i]); // } // // int64_t sum = 0; int cnt = 0; // for (int i = 0; i < n; i++) // if (disX[i] + disY[i] == disX[y]) { // sum += cost_level_one[i]; // ++cnt; // } // // for (int i = 0; i <= 2*n; i++) dp[n][i] = LLONG_MAX/2; // // dp[n][cnt] = sum; // // // for (int i = n-1; i >= 0; i--) { // for (int j = 0; j <= 2*n; j++) dp[i][j] = dp[i+1][j]; // if (disX[i] + disY[i] == disX[y]) { // for (int j = 0; j <= 2*n; j++) // if (j+1 <= 2*n) dp[i][j+1] = min(dp[i][j+1], dp[i+1][j] + cost_level_two[i] - cost_level_one[i]); // continue; // } // // for (int j = 0; j <= 2*n; j++) { // if (j+1 <= 2*n) dp[i][j+1] = min(dp[i][j+1], dp[i+1][j] + cost_level_one[i]); // if (j+2 <= 2*n) dp[i][j+2] = min(dp[i][j+2], dp[i+1][j] + cost_level_two[i]); // } // } // // int ans = 0; // for (int i = 0; i <= 2*n; i++) if (dp[0][i] <= k) ans = i; // return ans; // } // // int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { // n = N; x = X; y = Y; k = K; // for (int i = 0; i < N-1; i++) { // adj[U[i]].emplace_back(V[i], W[i]); // adj[V[i]].emplace_back(U[i], W[i]); // } // calcdisX(); calcdisY(); // int ans = max(sub1(), sub2()); // for (int i = 0; i < N; i++) adj[i].clear(); // for (int i = 0; i <= N; i++) for (int j = 0; j <= 2*N; j++) dp[i][j] = 0; // return ans; // } // //} // //int main() { // ios::sync_with_stdio(false); // cin.tie(NULL); // // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // // function<int64_t(int64_t, int64_t)> Rand = [&](int64_t l, int64_t h) { // return uniform_int_distribution<int64_t>(l, h)(rng); // }; // // while (1) { // int N = 1000, X = Rand(0, N-2), Y = Rand(X+1, N-1); int64_t K = Rand(1, 1'000'000'000'000'000'000LL); // // vector<int> U(N-1), V(N-1), W(N-1); // for (int i = 0; i < N-1; i++) { // U[i] = i+1; // V[i] = Rand(0, i); // W[i] = Rand(1, 1'000'000); // } // // if (max_score(N, X, Y, K, U, V, W) != sub_trau::max_score(N, X, Y, K, U, V, W)) { // cerr << "Wrong Answer!\nExpected Answer: " << sub_trau::max_score(N, X, Y, K, U, V, W) << "\n"; // cerr << "1\n" << N << ' ' << X << ' ' << Y << ' ' << K << "\n"; // for (int i = 0; i < N-1; i++) cerr << U[i] << ' ' << V[i] << ' ' << W[i] << "\n"; // exit(0); // } // cerr << "Correct!\n"; // } //} /* 1 5 1 2 92 1 0 75 2 1 2 3 1 88 4 3 54 */
#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...