Submission #1233277

#TimeUsernameProblemLanguageResultExecution timeMemory
1233277Ghulam_JunaidClosing Time (IOI23_closing)C++20
0 / 100
228 ms44292 KiB
#include <bits/stdc++.h> #include "closing.h" using namespace std; typedef long long ll; const int N = 2e5 + 10; int n, x[2]; ll k, dist[N][2]; vector<pair<int, int>> g[N]; void dfs(int v, int id, int p = -1){ for (auto [w, u] : g[v]){ if (u == p) continue; dist[u][id] = dist[v][id] + w; dfs(u, id, v); } } int max_score(int nn, int xx, int yy, ll kk, vector<int> uu, vector<int> vv, vector<int> ww){ n = nn, x[0] = xx, x[1] = yy, k = kk; for (int i = 0; i < n - 1; i ++){ g[uu[i]].push_back({ww[i], vv[i]}); g[vv[i]].push_back({ww[i], uu[i]}); } multiset<int> st[2]; for (int id : {0, 1}){ dist[x[id]][id] = 0; dfs(x[id], id); for (int i = 0; i < n; i ++) st[id].insert(dist[i][id]); } int ans = 0; while (st[0].size() and st[1].size()){ int a = *st[0].begin(), b = *st[1].begin(); if (a <= b){ if (k < a) break; k -= a; st[0].erase(st[0].begin()); ans++; continue; } if (k < b) break; k -= b; st[1].erase(st[1].begin()); ans++; continue; } for (int i = 0; i < n; i ++) g[i].clear(); return ans; }
#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...