Submission #990199

#	Time	Username	Problem	Language	Result	Execution time	Memory
990199		MilosMilutinovic	Special graph (IZhO13_specialg)	C++14	100 / 100	116 ms	32468 KiB

specialg

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
    if (a[i] == -1) {
      a[i] = i;
    }
  }
  int q;
  cin >> q;
  vector<int> op(q), x(q), y(q);
  for (int i = 0; i < q; i++) {
    cin >> op[i];
    if (op[i] == 1) {
      cin >> x[i];
      --x[i];
    } else {
      cin >> x[i] >> y[i];
      --x[i]; --y[i];
    }
  }
  vector<int> b(n, q);
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      b[x[i]] = i;
    }
  }
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    deg[a[i]] += 1;
  }
  vector<int> que;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      que.push_back(i);
    }
  }
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    deg[a[i]] -= 1;
    if (deg[a[i]] == 0) {
      que.push_back(a[i]);
    }
  }
  vector<bool> on_cyc(n, true);
  for (int i : que) {
    on_cyc[i] = false;
  }
  vector<int> dep(n);
  for (int b = (int) que.size() - 1; b >= 0; b--) {
    int i = que[b];
    dep[i] = dep[a[i]] + 1;
  }
  vector<int> pos(n);
  vector<int> idx(n, -1);
  vector<int> sz(n);
  int T = 0;
  for (int i = 0; i < n; i++) {
    if (!on_cyc[i] || idx[i] != -1) {
      continue;
    }
    int x = i;
    int ptr = 0;
    while (idx[x] == -1) {
      pos[x] = ptr;
      idx[x] = T;
      sz[T] += 1;
      ptr += 1;
      x = a[x];
    }
    T += 1;
  }
  const int L = 20;
  vector<vector<int>> jump(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    jump[i][0] = a[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      jump[i][j] = jump[jump[i][j - 1]][j - 1];
    }
  }
  vector<vector<int>> mn(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    mn[i][0] = b[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      mn[i][j] = min(mn[i][j - 1], mn[jump[i][j - 1]][j - 1]);
    }
  }
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  function<int(int)> root = [&](int x) {
    return p[x] == x ? x : p[x] = root(p[x]);
  };
  for (int i = 0; i < n; i++) {
    p[root(a[i])] = root(i);
  }
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      continue;
    }
    if (root(x[i]) != root(y[i]) || dep[x[i]] < dep[y[i]]) {
      cout << -1 << '\n';
      continue;
    }
    if (dep[y[i]] > 0) {
      int v = x[i];
      int d = dep[x[i]] - dep[y[i]];
      for (int i = L - 1; i >= 0; i--) {
        if (d >> i & 1) {
          v = jump[v][i];
        }
      }
      if (v != y[i]) {
        cout << -1 << '\n';
        continue;
      }
      v = x[i];
      int res = (int) 1e9;
      for (int i = L - 1; i >= 0; i--) {
        if (d >> i & 1) {
          res = min(res, mn[v][i]);
          v = jump[v][i];
        }
      }
      if (res >= i) {
        cout << d << '\n';
      } else {
        cout << -1 << '\n';
      }
      continue;
    }
    if (dep[x[i]] == 0) {
      int d = (pos[y[i]] - pos[x[i]] + sz[idx[x[i]]]) % sz[idx[x[i]]];
      int v = x[i];
      int res = (int) 1e9;
      for (int i = L - 1; i >= 0; i--) {
        if (d >> i & 1) {
          res = min(res, mn[v][i]);
          v = jump[v][i];
        }
      }
      if (res >= i) {
        cout << d << '\n';
      } else {
        cout << -1 << '\n';
      }
      continue;
    }
    int v = x[i];
    int d = 0;
    int res = (int) 1e9;
    {
      for (int i = L - 1; i >= 0; i--) {
        if (!on_cyc[jump[v][i]]) {
          res = min(res, mn[v][i]);
          d += (1 << i);
          v = jump[v][i];
        }
      }
      res = min(res, mn[v][0]);
      v = a[v];
      d += 1;
    }
    {
      int w = (pos[y[i]] - pos[v] + sz[idx[v]]) % sz[idx[v]];
      for (int i = L - 1; i >= 0; i--) {
        if (w >> i & 1) {
          res = min(res, mn[v][i]);
          d += (1 << i);
          v = jump[v][i];
        }
      }
    }
    if (res >= i) {
      cout << d << '\n';
    } else {
      cout << -1 << '\n';
    }
  }
  return 0;
}

• Subtask 1: 100 / 100