Submission #848710

#TimeUsernameProblemLanguageResultExecution timeMemory
848710math_rabbit_1028Closing Time (IOI23_closing)C++17
83 / 100
1049 ms44260 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; int n, x, y, ch[202020], ans; ll k, need[202020], dis[202020]; vector< pair<int, ll> > adj[202020]; priority_queue<pll> pq; int L, midp; vector< pair<int, ll> > path; void find_path(int v) { for (int i = 0; i < adj[v].size(); i++) { if (path.back().first == y) return; int u = adj[v][i].first; ll w = adj[v][i].second; if (ch[u] == 1) continue; ch[u] = 1; path.push_back({u, w}); find_path(u); if (path.back().first != y) path.pop_back(); } } int not_intersect() { int cnt = 0; for (int i = 0; i < n; i++) ch[i] = 0; while (!pq.empty()) pq.pop(); pq.push({-0, x}); pq.push({-0, y}); while (!pq.empty()) { int v = pq.top().second; ll w = -pq.top().first; pq.pop(); if (k - w >= 0) { cnt++; k -= w; } else break; ch[v] = 1; for (int i = 0; i < (int)adj[v].size(); i++) { if (ch[adj[v][i].first] == 1) continue; if (v == path[midp - 1].first && adj[v][i].first == path[midp].first) continue; if (v == path[midp].first && adj[v][i].first == path[midp - 1].first) continue; pq.push({-w-adj[v][i].second, adj[v][i].first}); } } return cnt; } ll dp[404040], nxt[404040]; void update(ll a, ll b) { for (int i = 0; i <= 2*n; i++) { ll val = dp[i]; if (i >= 1) val = min(val, dp[i - 1] + a); if (i >= 2) val = min(val, dp[i - 2] + b); nxt[i] = val; } for (int i = 0; i <= 2*n; i++) dp[i] = nxt[i]; } void DFS(int v, ll a, ll b) { for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].first; ll w = adj[v][i].second; if (ch[u] == 1) continue; ch[u] = 1; update(a + w, b + w); DFS(u, a + w, b + w); } } int intersect() { for (int i = 0; i < n; i++) ch[i] = 0; for (int i = 0; i <= L; i++) ch[path[i].first] = 1; for (int i = 0; i <= 2*n; i++) dp[i] = 2e18; dp[0] = 0; for (int i = 0; i < midp; i++) need[i] = dis[i] - dis[0]; for (int i = midp; i <= L; i++) need[i] = dis[L] - dis[i]; for (int i = 1; i <= L; i++) k -= need[i]; if (k < 0) return 0; for (int i = 0; i < midp; i++) { assert(dis[L] - dis[i] - need[i] >= 0); update(dis[L] - dis[i] - need[i], 2e18); ll a = dis[i] - dis[0]; ll b = dis[L] - dis[i]; assert(a <= b); DFS(path[i].first, a, b); } for (int i = midp; i <= L; i++) { assert(dis[i] - dis[0] - need[i] >= 0); update(dis[i] - dis[0] - need[i], 2e18); ll a = dis[L] - dis[i]; ll b = dis[i] - dis[0]; assert(a <= b); DFS(path[i].first, a, b); } int out = upper_bound(dp, dp + 2*n + 1, k) - dp - 1; return L + out + 1; } 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; ans = 0; for (int i = 0; i < n; i++) adj[i].clear(); path.clear(); for (int i = 0; i < (int)U.size(); i++) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } for (int i = 0; i < n; i++) ch[i] = 0; path.push_back({x, 0}); ch[x] = 1; find_path(x); assert(path.back().first == y); L = path.size() - 1; for (int i = 1; i <= L; i++) dis[i] = dis[i - 1] + path[i].second; for (int i = 0; i <= L; i++) { if (dis[i] - dis[0] > dis[L] - dis[i]) { midp = i; break; } } k = K; ans = not_intersect(); k = K; ans = max(ans, intersect()); return ans; }

Compilation message (stderr)

closing.cpp: In function 'void find_path(int)':
closing.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
closing.cpp: In function 'void DFS(int, ll, ll)':
closing.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < adj[v].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...