Submission #1243213

#TimeUsernameProblemLanguageResultExecution timeMemory
1243213nvujicaClosing Time (IOI23_closing)C++20
0 / 100
566 ms40496 KiB
#include "closing.h" #include <bits/stdc++.h> #define fi first #define se second #define ll long long #include <vector> using namespace std; const int maxn = 2e5 + 10; const ll inf = (1LL << 60); set <pair<ll, int> > s; vector <pair<int, int> > adj[maxn]; vector<pair<ll, int> > v1; vector<pair<ll, int> > v2; ll dist[maxn]; int max_score(int n, int a, int b, long long k, vector<int> u, vector<int> v, vector<int> w){ for(int i = 0; i < u.size(); i++){ adj[u[i]].push_back({v[i], w[i]}); adj[v[i]].push_back({u[i], w[i]}); } s.insert({0, a}); dist[a] = 0; // v1.push_back({0, 1}); for(int i = 0; i < n; i++){ if(i != a){ s.insert({inf, i}); dist[i] = inf; } } while(!s.empty()){ int x = (*s.begin()).se; s.erase(s.begin()); if(!v1.empty()) v1.push_back({v1.back().fi + dist[x], v1.size() + 1}); else v1.push_back({0, 1}); for(auto p: adj[x]){ int x2 = p.fi; int c = p.se; if(dist[x] + c < dist[x2]){ s.erase({dist[x2], x2}); dist[x2] = dist[x] + c; s.insert({dist[x2], x2}); } } } s.insert({0, b}); dist[b] = 0; // v2.push_back({0, 1}); for(int i = 0; i < n; i++){ if(i != b){ s.insert({inf, i}); dist[i] = inf; } } while(!s.empty()){ int x = (*s.begin()).se; s.erase(s.begin()); if(!v2.empty()) v2.push_back({v2.back().fi + dist[x], v2.size() + 1}); else v2.push_back({0, 1}); for(auto p: adj[x]){ int x2 = p.fi; int c = p.se; if(dist[x] + c < dist[x2]){ s.erase({dist[x2], x2}); dist[x2] = dist[x] + c; s.insert({dist[x2], x2}); } } } v2.push_back({inf, n + 1}); int ans = 0; for(int i = 0; i < v1.size(); i++){ ll cost = v1[i].fi; int br = v1[i].se; // cout << br << ' ' << cost << endl; if(k - cost < 0) continue; int p = lower_bound(v2.begin(), v2.end(), make_pair(k - cost + 1, 0)) - v2.begin(); p--; ans = max(ans, br + v2[p].se); } 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...