Submission #1306350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306350		rolandpetrean	도시들 (IOI15_towns)	C++20	25 / 100	10 ms	1852 KiB

towns

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

using ll = long long;
// #define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
using ti = array<int, 3>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
  int n;
  vector<int> par, sz;
  
  DSU(int n) {
    this->n = n;
    par.assign(n, 0);
    iota(par.begin(), par.end(), 0);
    sz.assign(n, 1);
  }
  
  int find(int a) {
    if (par[par[a]] != par[a]) {
      par[a] = find(par[a]);
    }
    return par[a];
  }
  void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) {
      return;
    }
    if (sz[a] < sz[b]) {
      swap(a, b);
    }
    sz[a] += sz[b];
    par[b] = a;
  }
};

int hubDistance(int n, int sub) {
  vector<int> dist0(n);
  pi maxi{-1, -1};
	for (int i = 0; i < n; ++i) {
    dist0[i] = getDistance(0, i);
    maxi = max(maxi, {dist0[i], i});
  }
  
  int u = maxi[1];
  maxi = {-1, -1};
  vector<int> distu(n);
  for (int i = 0; i < n; ++i) {
    distu[i] = getDistance(u, i);
    maxi = max(maxi, {distu[i], i});
  }
  auto [diam, v] = maxi;
  
  int pos0 = dist0[u] - (dist0[u] + dist0[v] - diam) / 2;
  int R = pos0;
  map<int, vector<int>> where;
  for (int i = 0; i < n; ++i) {
    // u ----|--0-- v
    // daca pos[i] >= pos[0] atunci chestia asta va da pozitia gresita dar va fi mereu >=pos[0] deci nu ne pasa pt R
    // ok de fapt asta e un lca
    int pos = distu[i] - (dist0[i] + distu[i] - distu[0]) / 2;
    if (pos < pos0) {
      R = min(R, max(pos, diam - pos));
      where[pos].pb(i);
    } else { // sunt in dreapta sau in subarborele ala
      where[pos0].pb(i);
    }
  }
  
  int cand = -1; // va fi maxim 1
  for (auto& [pos, v] : where) {
    if (pos == pos0 + 1) {
      continue;
    }
    if (max(pos, diam - pos) == R) {
      // se intampla maxim de 2 ori
      int left = 0, here = 0, right = 0;
      for (auto& [pos2, v2] : where) {
        if (pos2 < pos) {
          left += v2.size();
        } else if (pos2 == pos) {
          here += v2.size();
        } else if (pos2 > pos) {
          right += v2.size();
        }
      }
      
      if (left <= n / 2 && here <= n / 2 && right <= n / 2) {
        return R;
      }
      if (left <= n / 2 && right <= n / 2) {
        assert(cand == -1);
        cand = pos;
      }
    }
  }
  
  if (cand == -1) {
    return -R;
  }
  
  vector<int> rel = where[cand];
  int k = rel.size();
  DSU dsu(k);
  auto query = [&](int i, int j) -> bool { // true if lca != cand
    return (distu[i] + distu[j] - 2 * cand == getDistance(rel[i], rel[j]));
  };
  int now = -1, cnt = 0;
  for (int i = 0; i < k; ++i) {
    if (now == -1) {
      now = i;
      cnt = 1;
    } else {
      if (query(now, i)) {
        dsu.unite(i, now);
        ++cnt;
      } else {
        --cnt;
        if (cnt == 0) {
          now = -1;
        }
      }
    }
  }
  
  if (now == -1) {
    return R;
  }
  
  vector<bool> vis(k);
  now = dsu.find(now);
  vis[now] = true;
  int sz = dsu.sz[now];
  for (int i = 0; i < k; ++i) {
    int p = dsu.find(i);
    if (vis[p]) {
      continue;
    }
    vis[p] = true;
    if (query(now, p)) {
      sz += dsu.sz[p];
    }
  }
  
  if (sz <= n / 2) {
    return R;
  } else {
    return -R;
  }
}


/*

*/

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39