Submission #1238020

#TimeUsernameProblemLanguageResultExecution timeMemory
1238020SamAndClosing Time (IOI23_closing)C++20
8 / 100
97 ms34112 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 200005; int n; vector<pair<int, int> > g[N]; void dfs0(int x, int p, vector<ll>& d) { if (x == p) d[x] = 0; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i].fi; if (h == p) continue; d[h] = d[x] + g[x][i].se; dfs0(h, x, d); } } bool dfs1(int x, int p, int y, vector<int>& v) { v.push_back(x); if (x == y) return true; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i].fi; if (h == p) continue; if (dfs1(h, x, y, v)) return true; } v.pop_back(); return false; } bool c[N]; int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; for (int i = 0; i <= n + 1; ++i) { c[i] = false; g[i].clear(); } for (int i = 0; i < n - 1; ++i) { int x = U[i]; int y = V[i]; int z = W[i]; g[x].push_back(m_p(y, z)); g[y].push_back(m_p(x, z)); } vector<ll> dX(n); dfs0(X, X, dX); vector<ll> dY(n); dfs0(Y, Y, dY); vector<int> v; dfs1(X, X, Y, v); int ans = 0; { vector<ll> w; for (int x = 0; x < n; ++x) w.push_back(min(dX[x], dY[x])); sort(all(w)); ll k = K; for (int i = 0; i < n; ++i) { if (k >= w[i]) { k -= w[i]; ++ans; } } } ll k = K; int pans = 0; vector<ll> w1; for (int i = 0; i < sz(v); ++i) { if (k >= min(dX[v[i]], dY[v[i]])) { k -= min(dX[v[i]], dY[v[i]]); ++pans; w1.push_back(max(dX[v[i]], dY[v[i]]) - min(dX[v[i]], dY[v[i]])); } c[v[i]] = true; } if (pans != sz(v)) return ans; vector<pair<ll, int> > w; for (int x = 0; x < n; ++x) { if (c[x]) continue; w.push_back(m_p(min(dX[x], dY[x]), x)); } sort(all(w)); for (int i = -1; i < sz(w); ++i) { if (i >= 0) { int x = w[i].se; c[x] = true; k -= min(dX[x], dY[x]); ++pans; w1.push_back(max(dX[x], dY[x]) - min(dX[x], dY[x])); if (k < 0) break; } vector<ll> w2; for (int x = 0; x < n; ++x) { if (!c[x]) { w2.push_back(max(dX[x], dY[x])); } } sort(all(w2)); sort(all(w1)); vector<ll> p1, p2; p1.push_back(0); for (int i = 0; i < sz(w1); ++i) { p1.push_back(p1.back() + w1[i]); } p2.push_back(0); for (int i = 0; i < sz(w2); ++i) { p2.push_back(p2.back() + w2[i]); } for (int i = 0; i < sz(w1); ++i) { for (int j = 0; j < sz(w2); ++j) { if (k >= p1[i] + p2[j]) ans = max(ans, pans + i + 2 * j); } } } 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...