Submission #1248831

#TimeUsernameProblemLanguageResultExecution timeMemory
1248831madamadam3Closing Time (IOI23_closing)C++20
0 / 100
1093 ms20948 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; typedef long long ll; struct Edge { int v, w; }; int n, x, y; ll k; vi xi, yi, wi; vector<vector<Edge>> adj; const ll INF = 4e18; int disconnected() { int ans = 0; ll tl = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; q.push({0, x}), q.push({0, y}); vector<bool> vis(n, false); while (tl <= k && !q.empty()) { auto cur = q.top(); q.pop(); vis[cur.second] = true; if (tl + cur.first > k) break; tl += cur.first; ans++; for (auto &e : adj[cur.second]) { if (vis[e.v]) continue; q.push({cur.first + ll(e.w), e.v}); } } return ans; } int linear() { int best = 0; vector<ll> prefix(n+1, 0); for (int i = 1; i < n; i++) prefix[i+1] += prefix[i] + wi[i - 1]; for (int i1 = 0; i1 <= x; i1++) { for (int i2 = x; i2 < n; i2++) { for (int j1 = 0; j1 <= y; j1++) { for (int j2 = y; j2 < n; j2++) { int amt = (i2 - i1 + 1) + (j2 - j1 + 1); int jj = max(j1, i2 + 1); ll c = (prefix[i2+1] - prefix[i1]) + (prefix[j2+1] - prefix[jj]); if (c <= k) best = max(best, amt); } } } } return best; } int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) { n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W; adj.assign(n, vector<Edge>()); for (int i = 0; i < n - 1; i++) { adj[xi[i]].push_back(Edge{yi[i], wi[i]}); adj[yi[i]].push_back(Edge{xi[i], wi[i]}); } // return disconnected(); return linear(); }
#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...