oj.uz

Submission #410847

# Submission time Handle Problem Language Result Execution time Memory
410847 2021-05-23T20:00:21 Z erray Factories (JOI14_factories) C++11
33 / 100
 8000 ms 305248 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;
  SparseTable() { }
  SparseTable(vector<T> v, F _cal) : cal(_cal) {
    sz = (int) v.size();
    lg = 32 - __builtin_clz(sz);
    table.resize(lg);
    table[0] = v;
    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 = 31 - __builtin_clz(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;         
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)];
}

void Init(int n, int a[], int b[], int ws[]) {
  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);
  for (int i = 0; i < n; ++i) {
    int me = i;
    while (me != -1) {
      pars[i].push_back(me);
      me = par[me];
    }
  }
  debug(pars);
  debug("Init end /*--------------------------------------------------------------------------*/");
}

long long Query(int s, int x[], int t, int y[]) {
  vector<tuple<int, long long, int>> ev;
  for (int i = 0; i < s; ++i) {
    int v = x[i];
    for (auto e : pars[v]) {
      ev.push_back(make_tuple(e, Sp(e, v), 0));  
    }
  }

  for (int i = 0; i < t; ++i) {
    int v = y[i];
    for (auto e : pars[v]) {
      ev.push_back({e, Sp(e, v), 1});  
    }
  }
  sort(ev.begin(), ev.end());

  debug(ev);

  int lst = -1;
  const long long inf = (long long) 1e17;
  array<long long, 2> best = {inf, inf};
  long long res = inf;
  for (auto e : ev) {
    int v = get<0>(e);
    long long path = get<1>(e);
    int k = get<2>(e);
    debug(v, path, k, best);
    if (lst != v) {
      best = {inf, inf};
    }   
    best[k] = min(best[k], path);
    lst = v;
    res = min(res, best[0] + best[1]);
  }
  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1080 KB Output is correct
2 Correct 1812 ms 20388 KB Output is correct
3 Correct 2338 ms 19704 KB Output is correct
4 Correct 2479 ms 21988 KB Output is correct
5 Correct 3034 ms 21888 KB Output is correct
6 Correct 593 ms 19268 KB Output is correct
7 Correct 2305 ms 19568 KB Output is correct
8 Correct 2653 ms 22212 KB Output is correct
9 Correct 3044 ms 21992 KB Output is correct
10 Correct 598 ms 19380 KB Output is correct
11 Correct 2300 ms 19688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 3185 ms 226824 KB Output is correct
3 Correct 4165 ms 246080 KB Output is correct
4 Correct 1505 ms 207544 KB Output is correct
5 Correct 4497 ms 293172 KB Output is correct
6 Correct 4471 ms 246860 KB Output is correct
7 Correct 4132 ms 62548 KB Output is correct
8 Correct 921 ms 57896 KB Output is correct
9 Correct 3812 ms 68688 KB Output is correct
10 Correct 4168 ms 62860 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1080 KB Output is correct
2 Correct 1812 ms 20388 KB Output is correct
3 Correct 2338 ms 19704 KB Output is correct
4 Correct 2479 ms 21988 KB Output is correct
5 Correct 3034 ms 21888 KB Output is correct
6 Correct 593 ms 19268 KB Output is correct
7 Correct 2305 ms 19568 KB Output is correct
8 Correct 2653 ms 22212 KB Output is correct
9 Correct 3044 ms 21992 KB Output is correct
10 Correct 598 ms 19380 KB Output is correct
11 Correct 2300 ms 19688 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 3185 ms 226824 KB Output is correct
14 Correct 4165 ms 246080 KB Output is correct
15 Correct 1505 ms 207544 KB Output is correct
16 Correct 4497 ms 293172 KB Output is correct
17 Correct 4471 ms 246860 KB Output is correct
18 Correct 4132 ms 62548 KB Output is correct
19 Correct 921 ms 57896 KB Output is correct
20 Correct 3812 ms 68688 KB Output is correct
21 Correct 4168 ms 62860 KB Output is correct
22 Correct 6091 ms 247920 KB Output is correct
23 Correct 5511 ms 254024 KB Output is correct
24 Execution timed out 8048 ms 305248 KB Time limit exceeded
25 Halted 0 ms 0 KB -