Submission #1027441

#TimeUsernameProblemLanguageResultExecution timeMemory
1027441onbertRace (IOI11_race)C++17
100 / 100
1557 ms225768 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define int long long struct thing { int dist, d, u; bool operator < (const thing &b) const { if (dist!=b.dist) return dist < b.dist; if (d!=b.d) return d < b.d; return u < b.u; } }; struct node { pair<int,int> val; int lpt, rpt; }; const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18; int n, k; vector<pair<int,int>> adj[maxn]; int sz[maxn], dist[maxn], d[maxn]; bool cmp(pair<int,int> x, pair<int,int> y) { return sz[x.first] > sz[y.first]; } void dfs0(int u) { sz[u] = 1; for (auto [v, w]:adj[u]) { adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, w))); dist[v] = dist[u] + w, d[v] = d[u] + 1; dfs0(v); sz[u] += sz[v]; } sort(adj[u].begin(), adj[u].end(), cmp); } int newid[maxn], oldid[maxn], lim[maxn], cnt = -1; void dfs1(int u) { cnt++; newid[u] = cnt, oldid[cnt] = u; for (auto [v, w]:adj[u]) dfs1(v); lim[u] = cnt; } vector<node> seg[maxN]; void build(int id, int l, int r) { seg[id] = {{{-INF, -INF}, 0, 0}}; if (l==r) return; int mid = (l+r)/2; build(id*2, l, mid); build(id*2+1, mid+1, r); } void update(int id, int l, int r, int target, pair<int,int> val) { if (r<target || target<l) return; if (l==r) { seg[id].push_back({val, 0, 0}); return; } int mid = (l+r)/2; update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val); pair<int,int> cur = max(seg[id*2].back().val, seg[id*2+1].back().val); seg[id].push_back({cur, (int)seg[id*2].size()-1, (int)seg[id*2+1].size()-1}); } pair<int,int> qry(int id, int pt, int l, int r, int findl, int findr) { if (r<findl || findr<l) return {-INF, -INF}; if (findl<=l && r<=findr) return seg[id][pt].val; int mid = (l+r)/2; pair<int,int> lhs = qry(id*2, seg[id][pt].lpt, l, mid, findl, findr); pair<int,int> rhs = qry(id*2+1, seg[id][pt].rpt, mid+1, r, findl, findr); return max(lhs, rhs); } int ans = INF, curD; vector<thing> vec = {{-INF, -INF, -INF}}; void QRY(int l, int r, int val) { if (val<0) return; thing cur = {val, INF, INF}; int pos = upper_bound(vec.begin(), vec.end(), cur) - vec.begin() - 1; // cout << l << " " << r << " " << val << " " << pos << endl; pair<int,int> temp = qry(1, pos, 0, n-1, l, r); // cout << temp.first << " " << temp.second << endl; if (temp.first!=val) return; ans = min(-temp.second + curD, ans); } int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) { n = N, k = K; for (int i=0;i<n-1;i++) { auto [u, v] = H[i]; adj[u].push_back({v, L[i]}); adj[v].push_back({u, L[i]}); } dist[0] = 0, d[0] = 0; dfs0(0); dfs1(0); // for (int i=0;i<n;i++) cout << newid[i] << " "; cout << endl; for (int i=0;i<n;i++) vec.push_back({dist[i], -d[i], newid[i]}); sort(vec.begin(), vec.end()); build(1, 0, n-1); for (int i=1;i<=n;i++) { update(1, 0, n-1, vec[i].u, {vec[i].dist, vec[i].d}); // cout << i << " " << vec[i].u << " " << vec[i].dist << " " << vec[i].d << endl; } for (int u=0;u<n;u++) { curD = -d[u]; // if (u==6) cout << "TEST" << endl; QRY(newid[u]+1, lim[u], k + dist[u]); // if (u==6) cout << k+dist[u] << endl; for (int i=1;i<adj[u].size();i++) { int v = adj[u][i].first; for (int j=newid[v];j<=lim[v];j++) { curD = -2*d[u] + d[oldid[j]]; QRY(newid[u]+1, newid[v]-1, k + 2*dist[u] - dist[oldid[j]]); } } } if (ans==INF) return -1; return ans; }

Compilation message (stderr)

race.cpp: In function 'int32_t best_path(int32_t, int32_t, int32_t (*)[2], int32_t*)':
race.cpp:106:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i=1;i<adj[u].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...