Submission #716615

#	Time	Username	Problem	Language	Result	Execution time	Memory
716615		peijar	Prize (CEOI22_prize)	C++17	100 / 100	2678 ms	516088 KiB

Main

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e6;
const int MAXP = 20;
vector<int> adj[2][MAXN];
vector<pair<int, int>> toAdd[MAXN];
int depth[2][MAXN];

int par[2][MAXP][MAXN];

int tin[MAXN];

int getLca(int u, int v, int it) {
  if (depth[it][u] < depth[it][v])
    swap(u, v);
  int diff = depth[it][u] - depth[it][v];
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & diff)
      u = par[it][p][u];
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p)
    if (par[it][p][u] != par[it][p][v])
      u = par[it][p][u], v = par[it][p][v];
  return par[it][0][u];
}

void getDepths(int u, int it) {
  for (int v : adj[it][u]) {
    depth[it][v] = depth[it][u] + 1;
    getDepths(v, it);
  }
}

vector<int> choisis;
int nbSommets, K, Q, T;

void getFirst(int u) {
  if ((int)choisis.size() == K)
    return;
  choisis.push_back(u);
  for (int v : adj[0][u])
    getFirst(v);
}

int Time;
void dfsTime(int u) {
  tin[u] = Time++;
  for (int v : adj[1][u])
    dfsTime(v);
}

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

  cin >> nbSommets >> K >> Q >> T;

  array<int, 2> root;
  for (int it = 0; it < 2; ++it) {
    for (int i = 0; i < nbSommets; ++i) {
      int p;
      cin >> p;
      if (p == -1)
        root[it] = i, par[it][0][i] = i;
      else
        adj[it][p - 1].push_back(i), par[it][0][i] = p - 1;
    }

    for (int p = 0; p < MAXP - 1; ++p)
      for (int u = 0; u < nbSommets; ++u)
        par[it][p + 1][u] = par[it][p][par[it][p][u]];
    getDepths(root[it], it);
  }

  getFirst(root[0]);

  dfsTime(root[1]);

  for (int x : choisis)
    cout << x + 1 << ' ';
  cout << endl;

  sort(choisis.begin(), choisis.end(),
       [&](int u, int v) { return tin[u] < tin[v]; });
  vector<int> potentiels(nbSommets);
  vector<int> potentiels2(nbSommets);

  for (int i = 0; i < K - 1; ++i) {
    int u = choisis[i], v = choisis[i + 1];
    cout << "? " << u + 1 << ' ' << v + 1 << '\n';
  }
  cout << "!" << endl;
  for (int i = 0; i < K - 1; ++i) {
    int u = choisis[i], v = choisis[i + 1];
    int d1u, d1v, d2u, d2v;
    cin >> d1u >> d1v >> d2u >> d2v;
    potentiels[v] = potentiels[u] - d1u + d1v;
    potentiels2[v] = potentiels2[u] - d2u + d2v;
    int t = getLca(u, v, 1);
    potentiels2[t] = potentiels2[u] - d2u;
  }

  dbg(potentiels);
  dbg(potentiels2);

  vector<pair<int, int>> queries(T);
  for (auto &[u, v] : queries) {
    cin >> u >> v;
    --u, --v;
  }

  for (auto [u, v] : queries) {
    int lca = getLca(u, v, 0);
    int lca2 = getLca(u, v, 1);
    dbg(u + 1, v + 1);
    dbg(lca + 1);
    dbg(lca2);
    cout << potentiels[u] + potentiels[v] - 2 * potentiels[lca] << ' '
         << potentiels2[u] + potentiels2[v] - 2 * potentiels2[lca2] << '\n';
  }
  cout.flush();
}

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