Submission #1165657

#TimeUsernameProblemLanguageResultExecution timeMemory
1165657SmuggingSpunSwapping Cities (APIO20_swap)C++20
100 / 100
411 ms28776 KiB
#include<bits/stdc++.h> #include "swap.h" using namespace std; template<class T>void minimize(T& a, T b){ if(a > b){ a = b; } } template<class T>bool maximize(T& a, T b){ if(a < b){ a = b; } } const int lim = 1e5 + 5; const int INF = 1e9; bool is_sub1 = true, is_sub2; int n, m, u[lim << 1], v[lim << 1], w[lim << 1]; vector<int>ei, g[lim]; namespace sub1{ int max_w; void init(){ if(m == n){ max_w = *max_element(w, w + m); } } } namespace sub2{ int third; void init(){ if(n > 3){ vector<int>p(n - 1); iota(p.begin(), p.end(), 1); sort(p.begin(), p.end(), [&] (int i, int j){ return w[g[i][0]] < w[g[j][0]]; }); third = p[2]; } } } struct PersistentDSU{ vector<pair<int, int>>parent[lim], max_deg[lim]; int cache_time = -1, size[lim], deg[lim], cycle_time[lim]; void init(){ for(int i = 0; i < n; i++){ parent[i].emplace_back(-(size[i] = 1), i); max_deg[i].emplace_back(-1, deg[i] = 0); cycle_time[i] = INF; } } int find_set(int N, int time){ while(true){ int par_N = parent[N][upper_bound(parent[N].begin(), parent[N].end(), make_pair(time, INF)) - parent[N].begin() - 1].second; if(N == par_N){ break; } N = par_N; } return N; } void merge(int u, int v){ int U = u, V = v; if((u = find_set(u, ++cache_time)) != (v = find_set(v, cache_time))){ if(size[u] < size[v]){ swap(u, v); } parent[v].emplace_back(cache_time, u); size[u] += size[v]; } else{ minimize(cycle_time[u], cache_time); } int temp = max({max_deg[v].back().second, ++deg[U], ++deg[V]}); if(temp > max_deg[u].back().second){ max_deg[u].emplace_back(cache_time, temp); } } int get_max_deg(int N, int time){ return max_deg[N][upper_bound(max_deg[N].begin(), max_deg[N].end(), make_pair(time, INF)) - max_deg[N].begin() - 1].second; } bool have_cycle(int N, int time){ return cycle_time[N] <= time; } }; PersistentDSU dsu; void init(int N, int M, vector<int>U, vector<int>V, vector<int>W){ n = N; m = M; for(int i = 0; i < m; i++){ g[u[i] = U[i]].emplace_back(i); g[v[i] = V[i]].emplace_back(i); w[i] = W[i]; } for(int i = 0; i < n; i++){ if(g[i].size() > 2){ is_sub1 = false; break; } } if(is_sub1){ sub1::init(); return; } if(is_sub2 = (*max_element(u, u + m) == 0 && m == n - 1)){ sub2::init(); return; } dsu.init(); ei.resize(m); iota(ei.begin(), ei.end(), 0); sort(ei.begin(), ei.end(), [&] (int i, int j){ return w[i] < w[j]; }); for(int& i : ei){ dsu.merge(u[i], v[i]); } } int getMinimumFuelCapacity(int x, int y){ if(is_sub1){ return m == n - 1 ? -1 : sub1::max_w; } if(is_sub2){ if(x == 0){ return n < 4 ? -1 : max(w[g[y][0]], w[g[sub2::third][0]]); } return n < 4 ? -1 : max({w[g[x][0]], w[g[y][0]], w[g[sub2::third][0]]}); } int low = 0, high = m - 1, ans = -1; while(low <= high){ int mid = (low + high) >> 1, X = dsu.find_set(x, mid), Y = dsu.find_set(y, mid); if(X == Y && (dsu.have_cycle(X, mid) || dsu.get_max_deg(X, mid) > 2)){ ans = w[ei[mid]]; high = mid - 1; } else{ low = mid + 1; } } return ans; }

Compilation message (stderr)

swap.cpp: In function 'bool maximize(T&, T)':
swap.cpp:13:1: warning: no return statement in function returning non-void [-Wreturn-type]
   13 | }
      | ^
#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...