oj.uz

Submission #796425

# Submission time Handle Problem Language Result Execution time Memory
796425 2023-07-28T11:30:59 Z practice Prize (CEOI22_prize) C++14
100 / 100
 1978 ms 218272 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

const int K = 100010;
const int N = 1000100;

int n, k, q, t;
bool inset[N];
int L2[N];

struct Tree {
  int root;
  vector<int> adj[N];
} t1, t2;

struct CompressedTree {
  static const int LOG = 18;
  static const int SIZE = 2 * K;

  int dep[SIZE];
  int dad[SIZE][LOG];
  int dist[SIZE];
  vector<pair<int, int>> hints[SIZE];

  int comp_to_orig[SIZE];
  unordered_map<int, int> orig_to_comp;

  bool vis[SIZE];

  int Lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int start = L2[dep[a] - dep[b]];
    for (int i = start; i >= 0; --i) {
      if (dep[dad[a][i]] < dep[b]) continue;
      a = dad[a][i];
    }
    if (a == b) return a;
    start = L2[dep[a]];
    for (int i = start; i >= 0; --i) {
      if (dad[a][i] == dad[b][i]) continue;
      a = dad[a][i];
      b = dad[b][i];
    }
    return dad[a][0];
  }

  void AddHint(int a, int b, int d) {
    assert(dep[a] <= dep[b]);
    if (a == b) return;
    hints[a].emplace_back(b, d);
    hints[b].emplace_back(a, -d);
  }

  void Solve(int x = 0) {
    if (vis[x]) return;
    vis[x] = true;
    for (const auto& [y, d] : hints[x]) {
      dist[y] = dist[x] + d;
      //cout << d << " DEBUG\n";
      Solve(y);
    }
  }

  int Dist(int a_orig, int b_orig) {
    int a = orig_to_comp[a_orig];
    int b = orig_to_comp[b_orig];
    int l = Lca(a, b);
    return dist[a] - dist[l] + dist[b] - dist[l];
  }
} ct1, ct2;

struct Compressor {
  Tree& tree;
  CompressedTree& comp_tree;
  Compressor(Tree& tree, CompressedTree& comp_tree)
      : tree(tree), comp_tree(comp_tree) {}

  vector<int> vec;
  unordered_map<int, vector<int>> adj;

  int Dfs1(int x) {
    vector<int> children;
    for (int y : tree.adj[x]) {
      int r = Dfs1(y);
      if (r != 0) {
        children.push_back(r);
      }
    }
    if (inset[x] || children.size() > 1) {
      vec.push_back(x);
      adj.emplace(x, move(children));
      return x;
    }
    if (children.size() == 1) {
      return children[0];
    }
    return 0;
  }

  void Dfs2(int x, int dad = 0, int d = 0) {
    comp_tree.dep[x] = d;
    comp_tree.dad[x][0] = dad;
    FOR(i, 1, CompressedTree::LOG) {
      comp_tree.dad[x][i] = comp_tree.dad[comp_tree.dad[x][i - 1]][i - 1];
    }
    int x_orig = comp_tree.comp_to_orig[x];
    for (int y_orig : adj[x_orig]) {
      int y = comp_tree.orig_to_comp[y_orig];
      Dfs2(y, x, d + 1);
    }
  }

  void Compress() {
    vec.reserve(2 * k);
    Dfs1(tree.root);
    reverse(vec.begin(), vec.end());
    REP(i, vec.size()) {
      comp_tree.comp_to_orig[i] = vec[i];
      comp_tree.orig_to_comp[vec[i]] = i;
    }
    Dfs2(0);
  }
};

void LoadTree(Tree& tree) {
  REP(i, n) {
    int x;
    cin >> x;
    if (x == -1) {
      tree.root = i + 1;
    } else {
      tree.adj[x].push_back(i + 1);
    }
  }
}

vector<int> GetSet(Tree &tree) {
  vector<int> ret;
  ret.reserve(k);
  queue<int> qq;
  for (qq.push(tree.root); (int)ret.size() < k; qq.pop()) {
    int x = qq.front();
    ret.push_back(x);
    for (int y : tree.adj[x]) {
      qq.push(y);
    }
  }
  return ret;
}

vector<int> GetOrdered(Tree &tree) {
  vector<int> ret;
  ret.reserve(k);
  stack<int> s;
  for (s.push(tree.root); !s.empty();) {
    int x = s.top(); s.pop();
    if (inset[x]) ret.push_back(x);
    for (int y : tree.adj[x]) {
      s.push(y);
    }
  }
  assert((int)ret.size() == k);
  return ret;
}

void PrintSet(const vector<int>& S) {
  REP(i, k) {
    cout << S[i];
    if (i + 1 != k) cout << " ";
  }
  cout << endl;
}

void PrintQueries(const vector<int>& order) {
  REP(i, k - 1) {
    cout << "? " << order[i] << " " << order[i + 1] << "\n";
  }
  cout << "!" << "\n";
  cout.flush();
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k >> q >> t;
  LoadTree(t1);
  LoadTree(t2);

  L2[1] = 0;
  FOR(i, 2, N) L2[i] = L2[i / 2] + 1;

  vector<int> S = GetSet(t1);
  for (int x : S) inset[x] = true;
  PrintSet(S);

  vector<int> order = GetOrdered(t2);
  PrintQueries(order);

  Compressor(t1, ct1).Compress();
  Compressor(t2, ct2).Compress();

  REP(i, k - 1) {
    int a_orig = order[i];
    int b_orig = order[i + 1];
    int a1 = ct1.orig_to_comp[a_orig];
    int b1 = ct1.orig_to_comp[b_orig];
    int a2 = ct2.orig_to_comp[a_orig];
    int b2 = ct2.orig_to_comp[b_orig];
    int l1 = ct1.Lca(a1, b1);
    int l2 = ct2.Lca(a2, b2);
    int d1a, d1b, d2a, d2b;
    cin >> d1a >> d1b >> d2a >> d2b;
    ct1.AddHint(l1, a1, d1a);
    ct1.AddHint(l1, b1, d1b);
    ct2.AddHint(l2, a2, d2a);
    ct2.AddHint(l2, b2, d2b);
  }

  ct1.Solve();
  ct2.Solve();

  vector<pair<int, int>> queries;
  REP(i, t) {
    int a, b;
    cin >> a >> b;
    queries.emplace_back(a, b);
  }

  for (auto [a, b] : queries) {
    cout << ct1.Dist(a, b) << " " << ct2.Dist(a, b) << "\n";
  }
  cout.flush();

  return 0;
}

Compilation message

Main.cpp: In member function 'void CompressedTree::Solve(int)':
Main.cpp:62:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (const auto& [y, d] : hints[x]) {
      |                      ^
Main.cpp: In function 'int main()':
Main.cpp:235:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  235 |   for (auto [a, b] : queries) {
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 145444 KB Output is correct
2 Correct 1018 ms 156440 KB Output is correct
3 Correct 552 ms 102800 KB Output is correct
4 Correct 640 ms 101400 KB Output is correct
5 Correct 683 ms 110532 KB Output is correct
6 Correct 763 ms 114832 KB Output is correct
7 Correct 833 ms 114672 KB Output is correct
8 Correct 795 ms 112788 KB Output is correct
9 Correct 618 ms 102184 KB Output is correct
10 Correct 779 ms 107284 KB Output is correct
11 Correct 656 ms 98144 KB Output is correct
12 Correct 725 ms 105888 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 155852 KB Output is correct
2 Correct 964 ms 141848 KB Output is correct
3 Correct 701 ms 107552 KB Output is correct
4 Correct 756 ms 116060 KB Output is correct
5 Correct 648 ms 109796 KB Output is correct
6 Correct 883 ms 111832 KB Output is correct
7 Correct 1068 ms 122308 KB Output is correct
8 Correct 1121 ms 123448 KB Output is correct
9 Correct 915 ms 124132 KB Output is correct
10 Correct 901 ms 127236 KB Output is correct
11 Correct 848 ms 113920 KB Output is correct
12 Correct 855 ms 126132 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 123008 KB Output is correct
2 Correct 552 ms 123020 KB Output is correct
3 Correct 317 ms 77916 KB Output is correct
4 Correct 350 ms 77900 KB Output is correct
5 Correct 363 ms 77932 KB Output is correct
6 Correct 460 ms 87756 KB Output is correct
7 Correct 444 ms 87796 KB Output is correct
8 Correct 491 ms 87800 KB Output is correct
9 Correct 406 ms 85572 KB Output is correct
10 Correct 401 ms 85544 KB Output is correct
11 Correct 416 ms 85624 KB Output is correct
12 Correct 406 ms 85644 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1354 ms 185708 KB Output is correct
2 Correct 1348 ms 185848 KB Output is correct
3 Correct 832 ms 95680 KB Output is correct
4 Correct 877 ms 95576 KB Output is correct
5 Correct 952 ms 95552 KB Output is correct
6 Correct 1296 ms 114992 KB Output is correct
7 Correct 1250 ms 115088 KB Output is correct
8 Correct 1207 ms 115036 KB Output is correct
9 Correct 1107 ms 110824 KB Output is correct
10 Correct 1092 ms 110828 KB Output is correct
11 Correct 1115 ms 110852 KB Output is correct
12 Correct 1135 ms 110996 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1896 ms 218272 KB Output is correct
2 Correct 1978 ms 216628 KB Output is correct
3 Correct 1391 ms 122704 KB Output is correct
4 Correct 1580 ms 137452 KB Output is correct
5 Correct 1255 ms 119564 KB Output is correct
6 Correct 1777 ms 155808 KB Output is correct
7 Correct 1706 ms 140528 KB Output is correct
8 Correct 1742 ms 148820 KB Output is correct
9 Correct 1493 ms 143548 KB Output is correct
10 Correct 1511 ms 140436 KB Output is correct
11 Correct 1495 ms 140100 KB Output is correct
12 Correct 1548 ms 147800 KB Output is correct