Submission #1217897

#TimeUsernameProblemLanguageResultExecution timeMemory
1217897qwushaClosing Time (IOI23_closing)C++20
0 / 100
1097 ms2020928 KiB
#include <bits/stdc++.h> #include "closing.h" using namespace std; #define fi first #define se second typedef long long ll; typedef long double ld; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); ll inf = 1e18; ll n, x, y, k; vector<ll> u, v, w; vector<vector<pair<ll,ll>>> g; vector<ll> dist; void dfs(ll ve, ll d = 0, ll p = -1) { dist[ve] = min(dist[ve], d); for (auto [uv, le] : g[ve]) { if (uv == p) continue; dfs(uv, d + le, ve); } } int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) { n = N; x = X; y = Y; k = K; u.resize(N); v.resize(N); w.resize(N); g.resize(N); for (int i = 0; i < n - 1; i++) { u[i] = U[i]; v[i] = V[i]; w[i] = W[i]; g[v[i]].push_back({u[i], w[i]}); g[u[i]].push_back({v[i], w[i]}); } dist.assign(n, inf); dfs(x); dfs(y); sort(dist.begin(), dist.end()); int cnt = 0; for (int i = 0; i < n; i++) { if (dist[i] <= k) { cnt++; k -= dist[i]; } } return cnt; }
#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...