Submission #339304

#	Time	Username	Problem	Language	Result	Execution time	Memory
339304		boykut	Birthday gift (IZhO18_treearray)	C++14	12 / 100	4048 ms	10092 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

vector <int> g[200001];
vector <int> tree[200001];
int pred[200001], deep[200001], a[200001];

void make_tree(int v, int pre = -1) {
   pred[v] = pre;
   if (pre != -1) deep[v] = deep[pre] + 1;
   else deep[v] = 1;
   for (int to: g[v]) {
      if (to == pred[v]) continue;
      tree[v].push_back(to);
      make_tree(to, v);
   }
}

int lca(int a, int b) {
   while (deep[b] > deep[a]) b = pred[b];
   while (deep[a] > deep[b]) a = pred[a];
   if (a == b)
      return a;
   while (1) {
      a = pred[a];
      b = pred[b];
      if (a == b)
         return a;
   }
   return 1;
}

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n, m, q;
   cin >> n >> m >> q;
   for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i = 1; i <= m; i++) {
      cin >> a[i];
   }
   make_tree(1);
   for (int i = 0; i < q; i++) {
      int t;
      cin >> t;
      if (t == 1) {
         int pos, v;
         cin >> pos >> v;
         a[pos] = v;
      } else {
         int l, r, v;
         cin >> l >> r >> v;
         int ansx = -1, ansy = -1;
         int LC;
         bool find = false;
         for (int x = l; x <= r && !find; x++) {
            for (int y = x; y <= r && !find; y++) {
               if (y == x) LC = a[y];
               else LC = lca(LC, a[y]);
               if (LC == v) {
                  ansx = x, ansy = y;
                  find = true;
               }
            }
         }
         cout << ansx << ' ' << ansy << '\n';
      }
   }
   return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:21:27: warning: 'LC' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |    while (deep[b] > deep[a]) b = pred[b];
      |                     ~~~~~~^
treearray.cpp:60:14: note: 'LC' was declared here
   60 |          int LC;
      |              ^~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44