Submission #888934

#TimeUsernameProblemLanguageResultExecution timeMemory
888934ZHIRDILBILDIZClosing Time (IOI23_closing)C++17
0 / 100
1078 ms57224 KiB
#include<bits/stdc++.h> #include "closing.h" #define fi first #define se second #define ll long long using namespace std; const ll N = 2e5 + 10; bitset<N> us; vector<pair<ll, ll>> gr[N]; ll dist[N][2]; ll ds[N][2]; bool flag; void ultra_clear(ll n) { flag &= 0; for (ll i = 0; i < n; ++i) { for (ll j = 0; j < 2; ++j) dist[i][j] &= 0, ds[i][j] &= 0; gr[i].clear(); us[i] = 0; } } void pre_calc(ll city, ll last, ll type) { for (auto i : gr[city]) { if (i.fi == last) continue; dist[i.fi][type] = dist[city][type] + i.se; pre_calc(i.fi, city, type); } } void get_path(ll city, ll last, ll y, vector<ll> &path) { if (!flag) path.push_back(city); if (city == y) { flag = 1; return; } for (auto i : gr[city]) { if (i.fi == last) continue; get_path(i.fi, city, y, path); } if (!flag) path.pop_back(); } int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) { ultra_clear(n); int m = n - 1, ans = 0; for (ll i = 0; i < m; ++i) { gr[u[i]].push_back({v[i], w[i]}); gr[v[i]].push_back({u[i], w[i]}); } dist[x][0] = dist[y][1] &= 0; pre_calc(x, 0, 0); pre_calc(y, 0, 1); set<pair<ll, ll>> stx, sty; vector<ll> path; get_path(x, 0, y, path); ll psz = path.size() - 1; for (ll i = 0; i < path.size(); ++i) { for (ll j = 0; j < path.size(); ++j) { ll hp = k; ll cnt = 0; ll now[n] = {}; for (ll q = 0; q < n; ++q) ds[q][0] = dist[q][0], ds[q][1] = dist[q][1]; for (ll q = 0; q < i - 1; ++q) now[path[q]] = max(now[path[q]], dist[path[q]][0]); for (ll q = 0; q < j - 1; ++q) now[path[psz - q]] = max(now[path[psz - q]], dist[path[psz - q]][1]); for (ll q = 0; q <= psz; ++q) { for (ll z = 0; z < 2; ++z) ds[path[q]][z] = max(0ll, ds[path[q]][z] - now[path[q]]); hp -= now[path[q]]; } if (hp < 0) break; set<pair<ll, ll>> stx, sty; for (ll i = 0; i < n; ++i) stx.insert({ds[i][0], i}), sty.insert({ds[i][1], i}); while (stx.size() || sty.size()) { pair<ll, ll> p1 = {1e18, 1e18}, p2 = {1e18, 1e18}; if (stx.size()) p1 = *stx.begin(); if (sty.size()) p2 = *sty.begin(); if (p1.fi <= p2.fi) { if (hp - p1.fi < 0) break; hp -= p1.fi; sty.erase({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se}); now[p1.se] += p1.fi; stx.insert({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se}); stx.erase(stx.begin()); } else { if (hp - p2.fi < 0) break; hp -= p2.fi; stx.erase({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se}); now[p2.se] += p2.fi; stx.insert({max(0ll, dist[p1.se][0] - now[p2.se]), p2.se}); sty.erase(sty.begin()); } ++cnt; } ans = max((ll)ans, cnt); } } return ans; } //signed main() { // ios::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // int t; // cin >> t; // while (t--) { // int n; // int x, y; // ll k; // cin >> n >> x >> y >> k; // vector<int> u(n - 1), v(n - 1), w(n - 1); // for (int i = 0; i < n - 1; ++i) // cin >> u[i] >> v[i] >> w[i]; // cout << max_score(n, x, y, k, u, v, w); // } // return 0; //} //2 //7 0 2 10 //0 1 2 //0 3 3 //1 2 4 //2 4 2 //2 5 5 //5 6 3 //4 0 3 20 //0 1 18 //1 2 1 //2 3 19

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:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (ll i = 0; i < path.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
closing.cpp:61:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (ll j = 0; j < path.size(); ++j) {
      |                        ~~^~~~~~~~~~~~~
#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...