# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
843856 | 2023-09-04T16:03:24 Z | nonono | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KB |
#include "closing.h" #include <bits/stdc++.h> using namespace std; const int mxN = 200000; vector<vector<pair<int, int>>> adj(mxN); long long d[2][mxN]; void dfs(int u, int par, int type) { for(auto [v, w] : adj[u]) { if(v == par) continue ; d[type][v] = d[type][u] + w; dfs(v, u); } } int sub1(int N, long long K) { vector<long long> a; for(int i = 0; i < N; i ++) { a.push_back(d[0][i]); a.push_back(d[1][i]); } sort(a.begin(), a.end()); long long sum = 0; int ans = 0; for(long long x : a) { if(sum + x > K) break ; sum += x; ans += 1; } return ans; } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { for(int i = 0; i < N - 1; i ++) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } dfs(X, X, 0); dfs(Y, Y, 1); if(d[0][Y] > 2 * K) return sub1(N, K); } // int main() { // int N, X, Y; // long long K; // cin >> N >> X >> Y >> K; // vector<int> U(N), V(N), W(N); // for(int i = 0; i < N - 1; i ++) { // cin >> U[i] >> V[i] >> W[i]; // } // cout << max_score(N, X, Y, K, U, V, W) << "\n"; // return 0; // }