Submission #788634

#	Time	Username	Problem	Language	Result	Execution time	Memory
788634		WLZ	Prize (CEOI22_prize)	C++17	54 / 100	3545 ms	523912 KiB

Main

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

/** 1-indexed LCA class */
class least_common_ancestor {
  private:
    int n, max_log, dfs_cnt = 0, root;
    vector< vector< pair<int, int> > > g;
    vector< vector<int> > up;
    vector<int> d, dfs_in, dfs_out;

    void dfs(int u, int p) {
      dfs_in[u] = dfs_cnt++;
      up[u][0] = p;
      for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
      for (auto &v : g[u]) {
        if (v.first == u) continue;
        d[v.first] = d[u] + v.second;
        dfs(v.first, u);
      }
      dfs_out[u] = dfs_cnt;
    }

    void init() {
      n = (int) g.size() - 1;
      max_log = ceil(log2(n + 1));
      up.assign(n + 1, vector<int>(max_log + 1));
      d.assign(n + 1, 0);
      dfs_in.resize(n + 1);
      dfs_out.resize(n + 1);
      dfs(root, root);
    }
  public:
    /** Assumes g is an undirected tree. Can be directed if edges point away from vertex the root */
    least_common_ancestor(const vector< vector< pair<int, int> > > &_g, int _root = 1) : root(_root), g(_g) {
      init();
    }

    /** Assigns weight 1 to all edges in an unweighted tree */
    least_common_ancestor(const vector< vector<int> > &_g, int _root = 1) : root(_root) {
      g.assign((int) _g.size(), vector< pair<int, int> >());
      for (int i = 0; i < (int) _g.size(); i++) {
        for (auto &x : _g[i]) g[i].emplace_back(x, 1);
      }
      init();
    }

    bool is_anc(int u, int v) {
      return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
    }

    int query(int u, int v) {
      if (is_anc(u, v)) return u;
      if (is_anc(v, u)) return v;
      for (int i = max_log; i >= 0; i--) {
        if (!is_anc(up[u][i], v)) u = up[u][i];
      }
      return up[u][0];
    }

    int depth(int u) {
      return d[u];
    }

    int dist(int u, int v) {
      return d[u] + d[v] - 2 * d[query(u, v)];
    }

    int preorder(int u) {
      return dfs_in[u];
    }

    int postorder(int u) {
      return dfs_out[u];
    }
};

vector< vector< pair<int, int> > > v_g[2];

void dfs(int u, vector<int> &dist, const vector< vector< pair<int, int> > > &g) {
  if (dist[u] == -1) dist[u] = 0;
  for (auto &v : g[u]) {
    if (dist[v.first] == -1) {
      dist[v.first] = dist[u] + v.second;
      dfs(v.first, dist, g);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, q, t;
  cin >> n >> k >> q >> t;  
  int r[2];
  vector<int> p[2];
  vector< vector<int> > g[2];
  for (int idx = 0; idx < 2; idx++) {
    p[idx].resize(n + 1);
    g[idx].resize(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> p[idx][i];
      if (p[idx][i] == -1) r[idx] = i;
      else g[idx][p[idx][i]].push_back(i);
    }
  }
  least_common_ancestor lca[2] = {least_common_ancestor(g[0], r[0]), least_common_ancestor(g[1], r[1])};
  vector<int> x(n);
  iota(x.begin(), x.end(), 1);
  sort(x.begin(), x.end(), [&](int a, int b) {
    return lca[0].preorder(a) < lca[0].preorder(b);
  });
  x.erase(x.begin() + k, x.end());
  sort(x.begin(), x.end(), [&](int a, int b) {
    return lca[1].preorder(a) < lca[1].preorder(b);
  });
  vector<int> pos(n + 1, -1);
  for (int i = 0; i < k; i++) {
    if (i > 0) cout << ' ';
    cout << x[i];
    pos[x[i]] = i;
  }
  cout << endl;
  vector<int> virtual_tree = x;
  for (int i = 1; i < k; i++) {
    cout << "? " << x[i - 1] << ' ' << x[i] << endl;
    virtual_tree.push_back(lca[1].query(x[i - 1], x[i]));    
  }
  cout << "!" << endl;
  sort(virtual_tree.begin(), virtual_tree.end(), [&](int a, int b) {
    return lca[1].preorder(a) < lca[1].preorder(b);
  });
  virtual_tree.erase(unique(virtual_tree.begin(), virtual_tree.end()), virtual_tree.end());
  int v_r = virtual_tree[0];
  vector<int> l_0(k), r_0(k), l_1(k), r_1(k);
  v_g[0].assign(n + 1, vector< pair<int, int> >());
  v_g[1].assign(n + 1, vector< pair<int, int> >());
  for (int i = 1; i < k; i++) {
    cin >> l_0[i] >> r_0[i] >> l_1[i] >> r_1[i];
    int p_0 = lca[0].query(x[i - 1], x[i]), p_1 = lca[1].query(x[i - 1], x[i]);
    v_g[0][p_0].emplace_back(x[i - 1], l_0[i]);
    v_g[0][x[i - 1]].emplace_back(p_0, -l_0[i]);
    v_g[0][p_0].emplace_back(x[i], r_0[i]);
    v_g[0][x[i]].emplace_back(p_0, -r_0[i]);
    v_g[1][p_1].emplace_back(x[i - 1], l_1[i]);
    v_g[1][x[i - 1]].emplace_back(p_1, -l_1[i]);
    v_g[1][p_1].emplace_back(x[i], r_1[i]);
    v_g[1][x[i]].emplace_back(p_1, -r_1[i]);
  }
  vector<int> d_0(n + 1, -1), d_1(n + 1, -1);
  dfs(r[0], d_0, v_g[0]); dfs(v_r, d_1, v_g[1]);
  vector< pair<int, int> > queries(t);
  for (int i = 0; i < t; i++) cin >> queries[i].first >> queries[i].second;
  for (auto &e : queries) {
    int u = e.first, v = e.second;
    cout << d_0[u] + d_0[v] - 2 * d_0[lca[0].query(u, v)] << ' ' << d_1[u] + d_1[v] - 2 * d_1[lca[1].query(u, v)] << endl;
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24