Submission #414382

#	Time	Username	Problem	Language	Result	Execution time	Memory
414382		prvocislo	Swapping Cities (APIO20_swap)	C++17	30 / 100	2062 ms	524292 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, logn = 18, inf = 1e9 + 5;
struct edge { int t, w; };
vector<vector<edge> > g(maxn);
bool cmp(edge a, edge b) { return a.w < b.w; }
int n, m;
vector<vector<int> > l(logn, vector<int>(maxn, 0)), mx(logn, vector<int>(maxn, 0));
vector<int> d(maxn, 0), cr(maxn, inf);
int lca(int u, int v)
{
  if (d[u] < d[v]) swap(u, v); // u je hlbsie
  int ans = 0;
  for (int i = logn - 1; i >= 0; i--) if ((1 << i) & (d[u] - d[v])) ans = max(ans, mx[i][u]), u = l[i][u];
  if (u == v) return ans;
  for (int i = logn - 1; i >= 0; i--) if(l[i][u] != l[i][v])
  {
    ans = max({ans, mx[i][u], mx[i][v]});
    u = l[i][u], v = l[i][v];
  }
  return max({ans, mx[0][u], mx[0][v]});
}
set<pair<int, int> > s;
void dfs(int u, int p = -1)
{
  sort(g[u].begin(), g[u].end(), cmp);
  if (g[u].size() >= 3) 
    s.insert({ g[u][2].w, u});
  for (int i = 1; i < logn; i++) l[i][u] = l[i-1][l[i-1][u]], mx[i][u] = max(mx[i-1][u], mx[i-1][l[i-1][u]]);
  for (const edge &i : g[u])
  {
    if (i.t == p) continue;
    l[0][i.t] = u, mx[0][i.t] = i.w, d[i.t] = d[u] + 1;
    dfs(i.t, u);
  }
}
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]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
  dfs(0, -1);
  while (!s.empty())
  {
    int d = s.begin()->first, u = s.begin()->second;
    s.erase(s.begin());
    if (cr[u] < inf) continue;
    cr[u] = d;
    for (edge i : g[u]) 
      if (cr[i.t] == inf) 
        s.insert({max(d, i.w), i.t});
  }
}
int getMinimumFuelCapacity(int x, int y) {
  int ans = max(lca(x, y), min(cr[x], cr[y]));
  return ans == inf ? -1 : ans;
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 23 / 23
• Subtask 6: 0 / 27