oj.uz

Submission #865047

# Submission time Handle Problem Language Result Execution time Memory
865047 2023-10-24T04:14:00 Z xiaowuc1 Factories (JOI14_factories) C++17
100 / 100
 4373 ms 329952 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(0) cerr
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef int64_t ll;
typedef pair<int, int> pii;

mt19937 g1(0x48);
ll get_random_int(ll a, ll b) {
  return uniform_int_distribution<ll>(a, b)(g1);
}

struct koosaga {
  vector<vector<ll>> centroidtovertexdist; // <id, depth>
  vector<vector<int>> centroidtochildidx; // <id, depth>
  vector<vector<int>> centroidtochildcentroid;
  int n;
  int rootcentroid;
  ll qry(int currcentroid, int depth, vector<int>& lhs, vector<int>& rhs) {
    if(sz(lhs) == 0 || sz(rhs) == 0) return 1e18;
    ll ret = 1e18;
    ll lv = 1e18;
    ll rv = 1e18;
    {
      sort(all(lhs), [&](int a, int b) -> bool {
        return centroidtochildidx[a][depth] < centroidtochildidx[b][depth];
      });
      sort(all(rhs), [&](int a, int b) -> bool {
        return centroidtochildidx[a][depth] < centroidtochildidx[b][depth];
      });
    }
    int li = 0, ri = 0;
    if(lhs[li] == currcentroid) lv = 0, li++;
    if(rhs[ri] == currcentroid) rv = 0, ri++;
    while(li < sz(lhs) || ri < sz(rhs)) {
      int choice = 1e9;
      if(li < sz(lhs)) updmin(choice, centroidtochildidx[lhs[li]][depth]);
      if(ri < sz(rhs)) updmin(choice, centroidtochildidx[rhs[ri]][depth]);
      assert(choice >= 0);
      int nli = li;
      vector<int> nlv, nrv;
      while(nli < sz(lhs) && centroidtochildidx[lhs[nli]][depth] == choice) {
        nlv.pb(lhs[nli]);
        updmin(lv, centroidtovertexdist[lhs[nli++]][depth]);
      }
      int nri = ri;
      while(nri < sz(rhs) && centroidtochildidx[rhs[nri]][depth] == choice) {
        nrv.pb(rhs[nri]);
        updmin(rv, centroidtovertexdist[rhs[nri++]][depth]);
      }
      updmin(ret, qry(centroidtochildcentroid[currcentroid][choice], depth+1, nlv, nrv));
      li = nli;
      ri = nri;
    }
    return min(lv+rv, ret);
  }
  koosaga(){}
  koosaga(vector<array<int, 3>>& e) {
    n = sz(e) + 1;
    vector<int> nxtid(2*n-2, -1);
    vector<int> startid(n, -1);
    vector<int> to(2*n-2, -1);
    vector<int> weights(2*n-2);
    for(int i = 0; i < sz(e); i++) {
      auto [a, b, w] = e[i];
      to[2*i] = b;
      weights[2*i] = w;
      nxtid[2*i] = startid[a];
      startid[a] = 2*i;
      to[2*i+1] = a;
      weights[2*i+1] = w;
      nxtid[2*i+1] = startid[b];
      startid[b] = 2*i+1;
    }
    centroidtovertexdist.resize(n);
    centroidtochildidx.resize(n);
    centroidtochildcentroid.resize(n);
    rootcentroid = -1;
    vector<int> seen(n);
    vector<int> par(n);
    vector<int> treesz(n);
    vector<bool> processed(n);
    int centroiditer = 0;
    vector<int> postorder(n);
    vector<array<ll, 3>> q(n);
    auto init = y_combinator([&](auto initself, const int srcv) -> int {
      assert(!processed[srcv]);
      auto getcentroid = [&]() -> int {
        seen[srcv] = centroiditer++;
        int ql = 0;
        int qr = 0;
        postorder[qr++] = srcv;
        while(ql < qr) {
          int curr = postorder[ql++];
          treesz[curr] = 1;
          for(int id = startid[curr]; id >= 0; id = nxtid[id]) {
            int nv = to[id];
            if(!processed[nv] && seen[nv] != centroiditer) {
              seen[nv] = centroiditer;
              par[nv] = curr;
              postorder[qr++] = nv;
            }
          }
        }
        int totnodes = qr;
        for(int i = qr-1; i > 0; i--) {
          treesz[par[postorder[i]]] += treesz[postorder[i]];
          if(2*treesz[postorder[i]] >= totnodes) return postorder[i];
        }
        return srcv;
      };
      int centroid = getcentroid(); 
      centroidtochildidx[centroid].pb(-1);
      int childidx = 0;
      {
        int ql = 0;
        int qr = 0;
        q[qr++] = {centroid, 0, -1};
        while(ql < qr) {
          auto [v, w, p] = q[ql++];
          centroidtovertexdist[v].pb(w);
          if(p == centroid) centroidtochildidx[v].pb(childidx++);
          else if(p >= 0) centroidtochildidx[v].pb(centroidtochildidx[p].back());
          for(int id = startid[v]; id >= 0; id = nxtid[id]) {
            int nv = to[id];
            int nw = weights[id];
            if(processed[nv] || nv == p) continue;
            q[qr++] = {nv, w+nw, v};
          }
        }
      }
      processed[centroid] = true;
      for(int id = startid[centroid]; id >= 0; id = nxtid[id]) {
        int nv = to[id];
        if(processed[nv]) continue;
        centroidtochildcentroid[centroid].pb(initself(nv));
      }
      return centroid;
    });
    rootcentroid = init(get_random_int(0, n-1));
  }
};


koosaga koo;
void Init(int N, int A[], int B[], int D[]){
  vector<array<int, 3>> edges(N-1);
  for(int i = 0; i < N-1; i++) edges[i] = {A[i], B[i], D[i]};
  koo = koosaga(edges);
}

long long Query(int S, int X[], int T, int Y[]){
  vector<int> lhs(S), rhs(T);
  for(int i = 0; i < S; i++) lhs[i] = X[i];
  for(int i = 0; i < T; i++) rhs[i] = Y[i];
  return koo.qry(koo.rootcentroid, 0, lhs, rhs);
}

/*
void solve() {
  int n, q;
  cin >> n >> q;
  int *A = (int*)malloc(sizeof(int) * (n - 1));
  int *B = (int*)malloc(sizeof(int) * (n - 1));
  int *D = (int*)malloc(sizeof(int) * (n - 1));
  for(int a = 0; a < n - 1; a++){
    cin >> A[a] >> B[a] >> D[a];
  }
  Init(n, A, B, D);
  while(q--) {
    int S, T;	
    cin >> S >> T;
    int *X = (int*)malloc(sizeof(int) * S);
    int *Y = (int*)malloc(sizeof(int) * T);
    for(int b = 0; b < S; b++) cin >> X[b];
    for(int b = 0; b < T; b++) cin >> Y[b];
    cout << Query(S, X, T, Y) << "\n";
  }
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17024 KB Output is correct
2 Correct 539 ms 31800 KB Output is correct
3 Correct 669 ms 32436 KB Output is correct
4 Correct 444 ms 32340 KB Output is correct
5 Correct 690 ms 32468 KB Output is correct
6 Correct 327 ms 31412 KB Output is correct
7 Correct 609 ms 32440 KB Output is correct
8 Correct 449 ms 32172 KB Output is correct
9 Correct 715 ms 32300 KB Output is correct
10 Correct 331 ms 31568 KB Output is correct
11 Correct 616 ms 32316 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 2220 ms 223040 KB Output is correct
3 Correct 2915 ms 275904 KB Output is correct
4 Correct 858 ms 144604 KB Output is correct
5 Correct 3420 ms 323532 KB Output is correct
6 Correct 2961 ms 275868 KB Output is correct
7 Correct 1075 ms 69772 KB Output is correct
8 Correct 423 ms 52552 KB Output is correct
9 Correct 994 ms 78188 KB Output is correct
10 Correct 1012 ms 69904 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17024 KB Output is correct
2 Correct 539 ms 31800 KB Output is correct
3 Correct 669 ms 32436 KB Output is correct
4 Correct 444 ms 32340 KB Output is correct
5 Correct 690 ms 32468 KB Output is correct
6 Correct 327 ms 31412 KB Output is correct
7 Correct 609 ms 32440 KB Output is correct
8 Correct 449 ms 32172 KB Output is correct
9 Correct 715 ms 32300 KB Output is correct
10 Correct 331 ms 31568 KB Output is correct
11 Correct 616 ms 32316 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 2220 ms 223040 KB Output is correct
14 Correct 2915 ms 275904 KB Output is correct
15 Correct 858 ms 144604 KB Output is correct
16 Correct 3420 ms 323532 KB Output is correct
17 Correct 2961 ms 275868 KB Output is correct
18 Correct 1075 ms 69772 KB Output is correct
19 Correct 423 ms 52552 KB Output is correct
20 Correct 994 ms 78188 KB Output is correct
21 Correct 1012 ms 69904 KB Output is correct
22 Correct 2777 ms 227104 KB Output is correct
23 Correct 2448 ms 228848 KB Output is correct
24 Correct 4314 ms 281724 KB Output is correct
25 Correct 3893 ms 282508 KB Output is correct
26 Correct 3547 ms 282276 KB Output is correct
27 Correct 4373 ms 329952 KB Output is correct
28 Correct 1228 ms 151080 KB Output is correct
29 Correct 3524 ms 282008 KB Output is correct
30 Correct 3407 ms 281980 KB Output is correct
31 Correct 3387 ms 282252 KB Output is correct
32 Correct 1458 ms 77652 KB Output is correct
33 Correct 493 ms 52432 KB Output is correct
34 Correct 975 ms 65616 KB Output is correct
35 Correct 961 ms 66384 KB Output is correct
36 Correct 1194 ms 69488 KB Output is correct
37 Correct 1234 ms 69716 KB Output is correct