Submission #1042891

#TimeUsernameProblemLanguageResultExecution timeMemory
104289142kangarooClosing Time (IOI23_closing)C++17
100 / 100
143 ms47220 KiB
#include "closing.h" #include "bits/stdc++.h" #define ll long long using namespace std; struct Ed { ll to, w; }; bool operator<(const Ed &l, const Ed &r) { return l.w > r.w; } using g_t = vector<vector<Ed>>; void diDfs(int n, ll d, g_t &g, vector<ll> &di) { if (di[n] != -1) return; di[n] = d; for (auto e: g[n]) { diDfs(e.to, d + e.w, g, di); } } bool markdfs(int n, int p, int y, g_t &g, vector<bool> &ma) { if (n == y) return ma[n] = true; for (auto e: g[n]) { if (e.to == p) continue; if (markdfs(e.to, n, y, g, ma)) return ma[n] = true; } return false; } struct Score { ll med, mi, nu; }; bool operator<(const Score& l, const Score& r) { return tie(l.med, l.mi) < tie(r.med, r.mi); } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { g_t g(N); for (int i = 0; i < N - 1; ++i) { g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); } array<vector<ll>, 2> dist; dist.fill(vector<ll>(N, -1)); diDfs(X, 0, g, dist[0]); diDfs(Y, 0, g, dist[1]); int nuWithout = 0; vector<bool> vis(N, false); priority_queue<pair<Ed, bool>> q; q.push({{X, 0}, false}); q.push({{Y, 0}, true}); ll kC = K; while (!q.empty()) { auto [ed, com] = q.top(); q.pop(); if (vis[ed.to]) continue; if (kC < ed.w) break; kC -= ed.w; nuWithout++; vis[ed.to] = true; for (auto e: g[ed.to]) { q.push({{e.to, dist[com][e.to]}, com}); } } vector<bool> ma(N, false); markdfs(X, X, Y, g, ma); int nuW = 0; vector<Score> pos; for (int i = 0; i < N; ++i) { if (ma[i]) { K -= min(dist[0][i], dist[1][i]); nuW++; if (dist[0][i] == dist[1][i]) nuW++; else pos.push_back({2 * (max(dist[0][i], dist[1][i]) - min(dist[0][i], dist[1][i])), 2 * (max(dist[0][i], dist[1][i]) - min(dist[0][i], dist[1][i])), 1}); } else { bool co = dist[0][i] > dist[1][i]; if (dist[co][i] < dist[!co][i] - dist[co][i]) { pos.push_back({2*dist[co][i], 2*dist[co][i], 1}); pos.push_back({2*(dist[!co][i] - dist[co][i]), 2*(dist[!co][i] - dist[co][i]), 1}); } else { pos.push_back({dist[!co][i], 2*dist[co][i], 2}); } } } if (K < 0) return nuWithout; K *= 2; std::sort(pos.begin(), pos.end()); int laO = 0; for (int i = 0; i < pos.size(); ++i) { if (pos[i].med*pos[i].nu > K) { if (K + laO >= pos[i].med*2 && pos[i].nu == 2) { nuW++; K -= pos[i].med*2 - laO; laO = 0; } if (pos[i].mi <= K) { nuW++; K -= pos[i].mi; } } else { if (pos[i].nu == 1) laO = pos[i].med; K -= pos[i].med*pos[i].nu; nuW+=pos[i].nu; } } return max(nuW, nuWithout); } bool workDfs(int n, int p, bool up, g_t& g, int in) { if (!up && (in & (1 << n))) return false; for (auto e: g[n]) { if (e.to == p) continue; if (!workDfs(e.to, n, up && (in & (1 << n)), g, in)) return false; } return true; } int max_score2(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { g_t g(N); for (int i = 0; i < N - 1; ++i) { g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); } array<vector<ll>, 2> dist; dist.fill(vector<ll>(N, -1)); diDfs(X, 0, g, dist[0]); diDfs(Y, 0, g, dist[1]); int be = 2; for (int i = 0; i < 1 << 2*N; ++i) { ll su = 0; for (int j = 0; j < N; ++j) { if ((i & (1 << j)) && (i & (1 << (j + N)))) { su += max(dist[0][j], dist[1][j]); } else if (i & (1 << j)) su += dist[0][j]; else if(i & (1 << (j + N))) su += dist[1][j]; } if (su > K) continue; if (workDfs(X, X, true, g, i) && workDfs(Y, Y, true, g, i >> N)) be = max(be, __builtin_popcount(i)); } return be; }

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Score>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int i = 0; i < pos.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
#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...