oj.uz

Submission #716615

# Submission time Handle Problem Language Result Execution time Memory
716615 2023-03-30T14:43:39 Z peijar Prize (CEOI22_prize) C++17
100 / 100
 2678 ms 516088 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 << '\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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 294724 KB Output is correct
2 Correct 1149 ms 294932 KB Output is correct
3 Correct 1271 ms 268204 KB Output is correct
4 Correct 1275 ms 268248 KB Output is correct
5 Correct 1450 ms 268372 KB Output is correct
6 Correct 1365 ms 273636 KB Output is correct
7 Correct 1416 ms 273596 KB Output is correct
8 Correct 1409 ms 273604 KB Output is correct
9 Correct 1314 ms 268280 KB Output is correct
10 Correct 1359 ms 268404 KB Output is correct
11 Correct 1323 ms 268144 KB Output is correct
12 Correct 1414 ms 268296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1588 ms 295012 KB Output is correct
2 Correct 1232 ms 294616 KB Output is correct
3 Correct 1323 ms 268340 KB Output is correct
4 Correct 1473 ms 268468 KB Output is correct
5 Correct 1446 ms 268368 KB Output is correct
6 Correct 1507 ms 273624 KB Output is correct
7 Correct 1572 ms 273940 KB Output is correct
8 Correct 1623 ms 273748 KB Output is correct
9 Correct 1541 ms 272352 KB Output is correct
10 Correct 1497 ms 272372 KB Output is correct
11 Correct 1359 ms 272104 KB Output is correct
12 Correct 1467 ms 272376 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 293152 KB Output is correct
2 Correct 856 ms 293276 KB Output is correct
3 Correct 667 ms 266600 KB Output is correct
4 Correct 660 ms 266708 KB Output is correct
5 Correct 641 ms 266820 KB Output is correct
6 Correct 760 ms 272128 KB Output is correct
7 Correct 748 ms 272024 KB Output is correct
8 Correct 732 ms 272068 KB Output is correct
9 Correct 729 ms 270544 KB Output is correct
10 Correct 799 ms 270568 KB Output is correct
11 Correct 734 ms 270700 KB Output is correct
12 Correct 701 ms 270548 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1890 ms 515360 KB Output is correct
2 Correct 1973 ms 515212 KB Output is correct
3 Correct 1810 ms 462148 KB Output is correct
4 Correct 1673 ms 462200 KB Output is correct
5 Correct 1760 ms 462116 KB Output is correct
6 Correct 2037 ms 472848 KB Output is correct
7 Correct 1939 ms 472828 KB Output is correct
8 Correct 2558 ms 472792 KB Output is correct
9 Correct 2055 ms 469936 KB Output is correct
10 Correct 1986 ms 470140 KB Output is correct
11 Correct 2039 ms 469940 KB Output is correct
12 Correct 2149 ms 469984 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2183 ms 516016 KB Output is correct
2 Correct 2089 ms 516088 KB Output is correct
3 Correct 1993 ms 462836 KB Output is correct
4 Correct 2086 ms 462948 KB Output is correct
5 Correct 1964 ms 462764 KB Output is correct
6 Correct 2457 ms 473724 KB Output is correct
7 Correct 2614 ms 473344 KB Output is correct
8 Correct 2678 ms 473608 KB Output is correct
9 Correct 2261 ms 470740 KB Output is correct
10 Correct 2147 ms 470556 KB Output is correct
11 Correct 2170 ms 470792 KB Output is correct
12 Correct 2276 ms 470840 KB Output is correct