Submission #636979

#	Time	Username	Problem	Language	Result	Execution time	Memory
636979		abeker	Prize (CEOI22_prize)	C++17	100 / 100	2958 ms	391168 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24