oj.uz

Submission #716606

# Submission time Handle Problem Language Result Execution time Memory
716606 2023-03-30T14:25:24 Z peijar Prize (CEOI22_prize) C++17
0 / 100
 1604 ms 514472 KB 
#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 << endl;
  }
  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 delta = potentiels[root[0]];
  for (int u : choisis)
    potentiels[u] -= delta;
  int delta2 = potentiels2[root[1]];
  for (int u : choisis)
    potentiels2[u] -= delta2;
  dbg(potentiels);

  for (int i = 0; i < T; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    int lca = getLca(u, v, 0);
    int lca2 = getLca(u, v, 1);
    dbg(lca + 1);
    cout << potentiels[u] + potentiels[v] - 2 * potentiels[lca] << ' '
         << potentiels2[u] + potentiels2[v] - 2 * potentiels2[lca2] << endl;
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 767 ms 293144 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 293348 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 690 ms 292476 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1493 ms 513600 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1604 ms 514472 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -