oj.uz

답안 #842261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842261 2023-09-02T16:22:10 Z WLZ Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 524036 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2015 ms 302120 KB Output is correct
2 Correct 1990 ms 305344 KB Output is correct
3 Correct 1251 ms 256244 KB Output is correct
4 Correct 1195 ms 256204 KB Output is correct
5 Correct 1235 ms 258900 KB Output is correct
6 Correct 1684 ms 268260 KB Output is correct
7 Correct 1674 ms 268376 KB Output is correct
8 Correct 1643 ms 267492 KB Output is correct
9 Correct 1168 ms 256592 KB Output is correct
10 Correct 1225 ms 258412 KB Output is correct
11 Correct 1143 ms 254880 KB Output is correct
12 Correct 1218 ms 258260 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1757 ms 306000 KB Output is correct
2 Correct 1704 ms 301284 KB Output is correct
3 Correct 1268 ms 256608 KB Output is correct
4 Correct 1360 ms 259220 KB Output is correct
5 Correct 1299 ms 257672 KB Output is correct
6 Correct 1716 ms 266292 KB Output is correct
7 Correct 1851 ms 269804 KB Output is correct
8 Correct 1857 ms 270064 KB Output is correct
9 Correct 1641 ms 266300 KB Output is correct
10 Correct 1655 ms 267116 KB Output is correct
11 Correct 1524 ms 263328 KB Output is correct
12 Correct 1627 ms 267288 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1580 ms 294732 KB Output is correct
2 Correct 1576 ms 294688 KB Output is correct
3 Correct 887 ms 247588 KB Output is correct
4 Correct 877 ms 247152 KB Output is correct
5 Correct 879 ms 247596 KB Output is correct
6 Correct 1194 ms 258180 KB Output is correct
7 Correct 1183 ms 258496 KB Output is correct
8 Correct 1163 ms 258108 KB Output is correct
9 Correct 1024 ms 254368 KB Output is correct
10 Correct 1051 ms 254316 KB Output is correct
11 Correct 1034 ms 254392 KB Output is correct
12 Correct 1059 ms 254420 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3573 ms 524036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3558 ms 524016 KB Time limit exceeded
2 Halted 0 ms 0 KB -