oj.uz

Submission #636979

# Submission time Handle Problem Language Result Execution time Memory
636979 2022-08-30T23:20:39 Z abeker Prize (CEOI22_prize) C++17
100 / 100
 2958 ms 391168 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

class Tree {
  int n, lg, root;
  vector <vector <int>> ch, anc;
  vector <int> dist, dep;
public:
  Tree(int n) : n(n) {
    for (lg = 0; 1 << lg < n; lg++);
    ch.resize(n + 1);
    anc.resize(n + 1, vector <int> (lg + 1));
    dist.resize(n + 1);
    dep.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &anc[i][0]);
      if (anc[i][0] == -1) {
        anc[i][0] = 0;
        root = i;
      }
      else
        ch[anc[i][0]].push_back(i);
    }
  }
  Tree() {}
  void getSubset(int x, int k, vector <int> &v) {
    if (v.size() == k)
      return;
    v.push_back(x);
    for (auto it : ch[x])
      getSubset(it, k, v);
  }
  vector <int> getSubset(int k) {
    vector <int> res;
    getSubset(root, k, res);
    return res;
  }
  void getOrder(int x, vector <int> &v, const vector <bool> &in) {
    if (in[x])
      v.push_back(x);
    for (auto it : ch[x])
      getOrder(it, v, in);
  }
  vector <int> getOrder(const vector <int> &subset) {
    vector <bool> tmp(n + 1);
    for (auto it : subset)
      tmp[it] = true;
    vector <int> res;
    getOrder(root, res, tmp);
    return res;
  }
  int lca(int a, int b) {
    if (dep[a] < dep[b])
      swap(a, b);
    int diff = dep[a] - dep[b];
    for (int i = 0; i <= lg; i++)
      if (diff >> i & 1)
        a = anc[a][i];
    if (a == b)
      return a;
    for (int i = lg; i >= 0; i--)
      if (anc[a][i] != anc[b][i]) {
        a = anc[a][i];
        b = anc[b][i];
      }
    return anc[a][0];
  }
  void init(const vector <int> &order, const vector <pii> &ans) {
    for (int j = 1; j <= lg; j++)
      for (int i = 1; i <= n; i++)
        anc[i][j] = anc[anc[i][j - 1]][j - 1];
    queue <int> q;
    q.push(root);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (auto it : ch[x]) {
        dep[it] = dep[x] + 1;
        q.push(it);
      }
    }
    vector <int> l;
    for (int i = 1; i < order.size(); i++)
      l.push_back(lca(order[i - 1], order[i]));
    int pos = min_element(l.begin(), l.end(), [&](int x, int y) { return dep[x] < dep[y]; }) - l.begin();
    dist[order[pos]] = ans[pos].first;
    dist[order[pos + 1]] = ans[pos].second;
    for (int i = pos - 1; i >= 0; i--)
      dist[order[i]] = dist[order[i + 1]] - ans[i].second + ans[i].first;
    for (int i = pos + 2; i < order.size(); i++)
      dist[order[i]] = dist[order[i - 1]] - ans[i - 1].first + ans[i - 1].second;
    for (int i = 0; i < l.size(); i++)
      dist[l[i]] = dist[order[i]] - ans[i].first;
  }
  int getDistance(int a, int b) {
    int l = lca(a, b);
    return (dist[a] - dist[l]) + (dist[b] - dist[l]);
  }
};

int N, K, Q, T;
Tree one, two;

void load() {
  scanf("%d%d%d%d", &N, &K, &Q, &T);
  one = Tree(N);
  two = Tree(N);
}

void solve() {
  vector <int> subset = two.getOrder(one.getSubset(K));
  for (auto it : subset)
    printf("%d ", it);
  puts("");
  fflush(stdout);
  for (int i = 1; i < K; i++)
    printf("? %d %d\n", subset[i - 1], subset[i]);
  puts("!");
  fflush(stdout);
  vector <pii> ans_one, ans_two;
  for (int i = 1; i < K; i++) {
    int x, y, z, w;
    scanf("%d%d%d%d", &x, &y, &z, &w);
    ans_one.push_back({x, y});
    ans_two.push_back({z, w});
  }
  one.init(subset, ans_one);
  two.init(subset, ans_two);
  vector <pii> queries(T);
  for (auto &it : queries)
    scanf("%d%d", &it.first, &it.second);
  for (auto it : queries)
    printf("%d %d\n", one.getDistance(it.first, it.second), two.getDistance(it.first, it.second));
  fflush(stdout);
}

int main() {
  load();
  solve();
  return 0;
}

Compilation message

Main.cpp: In member function 'void Tree::getSubset(int, int, std::vector<int>&)':
Main.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if (v.size() == k)
      |         ~~~~~~~~~^~~~
Main.cpp: In member function 'void Tree::init(const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
Main.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 1; i < order.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:92:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = pos + 2; i < order.size(); i++)
      |                           ~~^~~~~~~~~~~~~~
Main.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'void load()':
Main.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d%d%d%d", &N, &K, &Q, &T);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In constructor 'Tree::Tree(int)':
Main.cpp:18:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |       scanf("%d", &anc[i][0]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d%d%d%d", &x, &y, &z, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d%d", &it.first, &it.second);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1580 ms 196564 KB Output is correct
2 Correct 1522 ms 197036 KB Output is correct
3 Correct 1056 ms 167900 KB Output is correct
4 Correct 990 ms 167896 KB Output is correct
5 Correct 1056 ms 168104 KB Output is correct
6 Correct 1527 ms 174680 KB Output is correct
7 Correct 1504 ms 174684 KB Output is correct
8 Correct 1459 ms 174632 KB Output is correct
9 Correct 1002 ms 167808 KB Output is correct
10 Correct 1065 ms 168008 KB Output is correct
11 Correct 992 ms 167788 KB Output is correct
12 Correct 1069 ms 167908 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1620 ms 197036 KB Output is correct
2 Correct 1543 ms 196376 KB Output is correct
3 Correct 1025 ms 167908 KB Output is correct
4 Correct 1109 ms 168056 KB Output is correct
5 Correct 1056 ms 167892 KB Output is correct
6 Correct 1522 ms 174176 KB Output is correct
7 Correct 1578 ms 174668 KB Output is correct
8 Correct 1608 ms 174708 KB Output is correct
9 Correct 1297 ms 172788 KB Output is correct
10 Correct 1335 ms 172812 KB Output is correct
11 Correct 1262 ms 172576 KB Output is correct
12 Correct 1305 ms 172876 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 194732 KB Output is correct
2 Correct 1142 ms 194712 KB Output is correct
3 Correct 748 ms 166032 KB Output is correct
4 Correct 748 ms 165820 KB Output is correct
5 Correct 757 ms 165864 KB Output is correct
6 Correct 1055 ms 172284 KB Output is correct
7 Correct 1006 ms 172300 KB Output is correct
8 Correct 1014 ms 172308 KB Output is correct
9 Correct 913 ms 170552 KB Output is correct
10 Correct 912 ms 170472 KB Output is correct
11 Correct 914 ms 170536 KB Output is correct
12 Correct 894 ms 170572 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2732 ms 389108 KB Output is correct
2 Correct 2660 ms 389256 KB Output is correct
3 Correct 1747 ms 331880 KB Output is correct
4 Correct 1702 ms 331496 KB Output is correct
5 Correct 1728 ms 331468 KB Output is correct
6 Correct 2525 ms 344636 KB Output is correct
7 Correct 2426 ms 344980 KB Output is correct
8 Correct 2428 ms 344668 KB Output is correct
9 Correct 2194 ms 340864 KB Output is correct
10 Correct 2176 ms 340924 KB Output is correct
11 Correct 2143 ms 341092 KB Output is correct
12 Correct 2143 ms 340984 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2958 ms 391168 KB Output is correct
2 Correct 2943 ms 390940 KB Output is correct
3 Correct 1868 ms 333320 KB Output is correct
4 Correct 1943 ms 333824 KB Output is correct
5 Correct 1878 ms 333272 KB Output is correct
6 Correct 2840 ms 346456 KB Output is correct
7 Correct 2771 ms 345740 KB Output is correct
8 Correct 2803 ms 346392 KB Output is correct
9 Correct 2319 ms 342172 KB Output is correct
10 Correct 2401 ms 342164 KB Output is correct
11 Correct 2396 ms 342128 KB Output is correct
12 Correct 2390 ms 342544 KB Output is correct