oj.uz

Submission #410858

# Submission time Handle Problem Language Result Execution time Memory
410858 2021-05-23T20:30:35 Z erray Factories (JOI14_factories) C++11
100 / 100
 4365 ms 418864 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
 template<typename A, typename B> string to_string(pair<A, B> p);
template<typename A, typename B, typename C> string to_string(tuple<A, B, C> t);
template<typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> t);

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string("'") + c + "'";
}

string to_string(const char* c) {
  return to_string(string(c));
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}

string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (i > 0) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& e : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(e);
  }
  res += "}";
  return res;
}

template<typename A, typename B> string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
template<typename A, typename B, typename C> string to_string(tuple<A, B, C> t) {
  return '(' + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + '}';
}
template<typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> t) {
  return '(' + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + '}';   
}

void debug_out() {
  cerr << endl;
}

template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << "  " << to_string(H);
  debug_out(T...);
}

#ifdef DEBUG 
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) void(37)
#endif

template<typename T, typename F = function<T(const T&, const T&)>> struct SparseTable {
  int sz, lg;
  vector<vector<T>> table;
  F cal;
  vector<int> LG;
  SparseTable() { }
  SparseTable(vector<T> v, F _cal) : cal(_cal) {
    sz = (int) v.size();
    lg = 32 - __builtin_clz(sz);
    table.resize(lg);
    table[0] = v;
    LG.resize(sz + 1);
    int cur = 2;
    for (int i = 1; i <= sz; ++i) {
      LG[i] = LG[i - 1];
      if (i == cur) {
        cur <<= 1;
        LG[i]++;
      }
    }
    debug(LG);
    for (int i = 1; i < lg; ++i) {
      table[i].resize(sz - (1 << i) + 1);
      assert(sz - (1 << i) + 1 >= 0);
      for (int j = 0; j < (int) table[i].size(); ++j) {
        table[i][j] = cal(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  T get(int l, int r) {
    assert(l >= 0 && r < sz && l <= r);
    int clg = LG[r - l + 1];
    return cal(table[clg][l], table[clg][r - (1 << clg) + 1]);
  }
};

vector<vector<int>> pars;
SparseTable<int> st;
vector<int> tour;
vector<int> stime;
vector<int> etime;
vector<long long> d;
vector<vector<long long>> sp;   
vector<long long> best;
int Lca (int x, int y) {
  if (stime[x] > stime[y]) {
    swap(x, y);
  }
  if (etime[x] >= etime[y]) {
    return x;
  }
  return st.get(etime[x], stime[y]);
}

long long Sp(int x, int y) {
  return d[x] + d[y] - 2 * d[Lca(x, y)];
}


const long long inf = (long long) 1e17;
void Init(int n, int a[], int b[], int ws[]) {
  best.resize(n, inf);
  debug("hi");
  vector<vector<pair<int, int>>> wg(n);
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    wg[a[i]].emplace_back(b[i], ws[i]);
    wg[b[i]].emplace_back(a[i], ws[i]);
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  

  d.resize(n);
  stime.resize(n);
  etime.resize(n);
  vector<int> size(n, 1);
  function<void(int, int)> Pre_dfs = [&](int v, int pr) {      
    debug(v, pr);
    stime[v] = etime[v] = int(tour.size());
    tour.push_back(v);
    for (auto e : wg[v]) {
      int u, w;
      tie(u, w) = e;
      if (u == pr) {
        continue;
      }
      d[u] = d[v] + w;
      Pre_dfs(u, v);
      size[v] += size[u];
      etime[v] = int(tour.size());
      tour.push_back(v);
    }  
  };
  Pre_dfs(0, -1);
  st = SparseTable<int>(tour, [&](int x, int y) {
    return (d[x] < d[y] ? x : y);
  });
  debug(d, tour, stime, etime); 
  debug(size);


  vector<int> par(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    if (size[v] == 0) {
      return;
    }
    int no = -1;
    debug(v, pr);
    for (auto u : g[v]) {
      if (size[u] > size[v] / 2) {
        assert(no == -1);
        no = u;
      }
    }
    if (no == -1) {
      par[v] = pr;
      size[v] = 0;
      debug("look at me, I'm the root now", v);
      for (auto u : g[v]) {
        Dfs(u, v);
      }
    } else {
      size[v] -= size[no];
      size[no] += size[v];
      debug(size[v], size[no]);
      Dfs(no, pr);
    }
  }; 
  Dfs(0, -1);
  debug(par);
  pars.resize(n);
  sp.resize(n);
  for (int i = 0; i < n; ++i) {
    int me = i;
    while (me != -1) {
      pars[i].push_back(me);
      sp[i].push_back(Sp(i, me));
      me = par[me];
    }
  }
  debug(pars);
  debug(sp);
  debug("Init end /*--------------------------------------------------------------------------*/");
}

long long Query(int s, int x[], int t, int y[]) {
  for (int j = 0; j < s; ++j) {
    int v = x[j];
    for (int i = 0; i < int(pars[v].size()); ++i) {
      int u = pars[v][i];
      best[u] = min(best[u], sp[v][i]);
    }
  }
  long long res = inf;
  for (int j = 0; j < t; ++j) {
    int v = y[j];
    for (int i = 0; i < int(pars[v].size()); ++i) {
      int u = pars[v][i];
      res = min(res, best[u] + sp[v][i]);
    }
  }
  
  for (int j = 0; j < s; ++j) {
    int v = x[j];
    for (int i = 0; i < int(pars[v].size()); ++i) {
      int u = pars[v][i];
      best[u] = inf;
    }
  }
  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 370 ms 11600 KB Output is correct
3 Correct 366 ms 11940 KB Output is correct
4 Correct 362 ms 11908 KB Output is correct
5 Correct 395 ms 12492 KB Output is correct
6 Correct 269 ms 11308 KB Output is correct
7 Correct 374 ms 12048 KB Output is correct
8 Correct 355 ms 11964 KB Output is correct
9 Correct 394 ms 12408 KB Output is correct
10 Correct 264 ms 11248 KB Output is correct
11 Correct 365 ms 12000 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2644 ms 293904 KB Output is correct
3 Correct 3182 ms 346588 KB Output is correct
4 Correct 1460 ms 224592 KB Output is correct
5 Correct 3552 ms 418864 KB Output is correct
6 Correct 3365 ms 346140 KB Output is correct
7 Correct 1174 ms 68148 KB Output is correct
8 Correct 682 ms 52632 KB Output is correct
9 Correct 1218 ms 78504 KB Output is correct
10 Correct 1200 ms 68364 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 370 ms 11600 KB Output is correct
3 Correct 366 ms 11940 KB Output is correct
4 Correct 362 ms 11908 KB Output is correct
5 Correct 395 ms 12492 KB Output is correct
6 Correct 269 ms 11308 KB Output is correct
7 Correct 374 ms 12048 KB Output is correct
8 Correct 355 ms 11964 KB Output is correct
9 Correct 394 ms 12408 KB Output is correct
10 Correct 264 ms 11248 KB Output is correct
11 Correct 365 ms 12000 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2644 ms 293904 KB Output is correct
14 Correct 3182 ms 346588 KB Output is correct
15 Correct 1460 ms 224592 KB Output is correct
16 Correct 3552 ms 418864 KB Output is correct
17 Correct 3365 ms 346140 KB Output is correct
18 Correct 1174 ms 68148 KB Output is correct
19 Correct 682 ms 52632 KB Output is correct
20 Correct 1218 ms 78504 KB Output is correct
21 Correct 1200 ms 68364 KB Output is correct
22 Correct 3189 ms 295376 KB Output is correct
23 Correct 3253 ms 297632 KB Output is correct
24 Correct 4082 ms 348140 KB Output is correct
25 Correct 4110 ms 350080 KB Output is correct
26 Correct 4002 ms 349508 KB Output is correct
27 Correct 4365 ms 413664 KB Output is correct
28 Correct 1794 ms 228104 KB Output is correct
29 Correct 3948 ms 348600 KB Output is correct
30 Correct 3955 ms 347968 KB Output is correct
31 Correct 3993 ms 348772 KB Output is correct
32 Correct 1358 ms 78376 KB Output is correct
33 Correct 719 ms 51896 KB Output is correct
34 Correct 1050 ms 62696 KB Output is correct
35 Correct 982 ms 63372 KB Output is correct
36 Correct 1175 ms 66764 KB Output is correct
37 Correct 1169 ms 66792 KB Output is correct