Submission #1074965

#TimeUsernameProblemLanguageResultExecution timeMemory
1074965bleahbleahClosing Time (IOI23_closing)C++17
100 / 100
203 ms47168 KiB
#include "closing.h" #include <vector> #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; const int nmax = 2e5 + 5; ll dx[nmax], dy[nmax]; int p[nmax]; vector<pii> g[nmax]; void filld(int node, int f, ll *d) { p[node] = f; for(auto [x, c] : g[node]) { if(x == f) continue; d[x] = d[node] + c; filld(x, node, d); } return; } int separate(int N, ll S) { vector<pii> s; for(int i = 0; i < N; i++) { s.emplace_back(i, 1); s.emplace_back(i, 2); } sort(all(s), [&](auto a, auto b) { return (a.second == 1? dx[a.first] : dy[a.first]) < (b.second == 1? dx[b.first] : dy[b.first]); }); vector<int> occ(N, 0); int cnt = 0; for(auto [x, t] : s) { if(occ[x]) continue; auto C = (t == 1? dx[x] : dy[x]); if(S < C) break; S -= C; occ[x] = 1; cnt++; } return cnt; } signed max_score(signed N, signed X, signed Y, long long S, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) { for(int i = 0; i <= N; i++) g[i].clear(); for(int i = 0; i < sz(U); i++) { g[U[i]].emplace_back(V[i], W[i]); g[V[i]].emplace_back(U[i], W[i]); } dx[X] = dy[Y] = 0; filld(X, X, dx); filld(Y, Y, dy); const int opt1 = separate(N, S); //cerr << opt1 << '\n'; vector<int> onchain(N, 0); int t = X; while(t != Y) { onchain[t] = 1; t = p[t]; } onchain[Y] = 1; vector<pair<ll, ll>> s; int opt2 = 0; for(int node = 0; node < N; node++) { //cerr << onchain[node] << ' '; if(onchain[node]) { int a = dx[node], b = dy[node]; if(a > b) swap(a, b); S -= a; s.emplace_back(b - a, -1); opt2++; } else { int a = dx[node], b = dy[node]; if(a > b) swap(a, b); b -= a; if(a <= b) { s.emplace_back(a, -1); s.emplace_back(b, -1); } else { s.emplace_back(a, b); } } } //cerr << '\n' << S << '\n'; if(S < 0) return opt1; sort(all(s), [&](auto a, auto b) { auto C = (a.second == -1? 2 * a.first : a.first + a.second); auto D = (b.second == -1? 2 * b.first : b.first + b.second); return C < D; }); //for(auto [a, b] : s) cerr << a << ' ' << b << '\n'; auto simulate = [&s](int start, int S) { int cnt = 0; for(int it = start; it < sz(s); it++) { auto [a, b] = s[it]; if(b == -1) { if(a > S) break; S -= a; cnt++; } else { if(a + b > S) { for(int j = it + 1; j < sz(s); j++) a = min(a, s[j].first); if(S < a) break; cnt++; break; } else { S -= a + b; cnt += 2; } } } return cnt; }; vector<int> oper1; vector<pii> oper2; for(int it = 0; it < sz(s); it++) { auto [a, b] = s[it]; if(b == -1) { if(a > S) break; S -= a; opt2++; oper1.emplace_back(a); } else { if(a + b > S) { int mx = simulate(it, S); if(sz(oper1)) { mx = max(simulate(it, S + oper1.back()) - 1, mx); } if(sz(oper2)) { auto [yi, er] = oper2.back(); mx = max(simulate(it, S + er) - 1, mx); mx = max(simulate(it, S + yi + er) - 2, mx); } if(sz(oper1) && sz(oper2)) { auto [yi, er] = oper2.back(); mx = max(simulate(it, S + yi + er + oper1.back()) - 3, mx); } opt2 += mx; break; } else { S -= a + b; oper2.emplace_back(a, b); opt2 += 2; } } } return max(opt1, opt2); } #undef int
#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...