Submission #19550165


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  long N, Q;
  cin >> N;
  vector<vector<long>> g(N), p(30, vector<long>(N));
  deque<long> dq;
  for (long i = 0; i < N; i++) {
    cin >> p[0][i];
    if (p[0][i] == -1) {
      p[0][i] = i;
      dq.push_back(i);
      continue;
    }
    g[--p[0][i]].push_back(i);
  }

  vector<long> rank(N, 0);
  rank[dq.front()] = 1;
  while (!dq.empty()) {
    long now = dq.front();  dq.pop_front();
    for (auto next : g[now]) {
      if (rank[next] != 0)  continue;
      rank[next] = rank[now] + 1;
      dq.push_back(next);
    }
  }

  for (int i = 1; i < 30; i++)
    for (long j = 0; j < N; j++)
      p[i][j] = p[i-1][p[i-1][j]];

  cin >> Q;
  while (Q--) {
    long a, b;  cin >> a >> b;
    long h = rank[--a] - rank[--b];
    for (long i = 29; i >= 0; i--)
      if (1 << i <= h) {
	a = p[i][a];
	h -= 1 << i;
      }
    cout << (a == b ? "Yes" : "No") << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task K - Conglomerate
User kempo_o
Language C++ (GCC 9.2.1)
Score 6
Code Size 999 Byte
Status AC
Exec Time 338 ms
Memory 47860 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 2
AC × 36
Set Name Test Cases
Sample example_01.txt, example_02.txt
All example_01.txt, example_02.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt
Case Name Status Exec Time Memory
example_01.txt AC 10 ms 3464 KB
example_02.txt AC 2 ms 3520 KB
subtask_01_01.txt AC 272 ms 42852 KB
subtask_01_02.txt AC 107 ms 40664 KB
subtask_01_03.txt AC 268 ms 40988 KB
subtask_01_04.txt AC 179 ms 7144 KB
subtask_01_05.txt AC 191 ms 7220 KB
subtask_01_06.txt AC 45 ms 16344 KB
subtask_01_07.txt AC 274 ms 45844 KB
subtask_01_08.txt AC 274 ms 45832 KB
subtask_01_09.txt AC 275 ms 45764 KB
subtask_01_10.txt AC 281 ms 45852 KB
subtask_01_11.txt AC 296 ms 47628 KB
subtask_01_12.txt AC 297 ms 47856 KB
subtask_01_13.txt AC 334 ms 47668 KB
subtask_01_14.txt AC 326 ms 47700 KB
subtask_01_15.txt AC 296 ms 47748 KB
subtask_01_16.txt AC 292 ms 47760 KB
subtask_01_17.txt AC 330 ms 47688 KB
subtask_01_18.txt AC 338 ms 47668 KB
subtask_01_19.txt AC 294 ms 47800 KB
subtask_01_20.txt AC 295 ms 47748 KB
subtask_01_21.txt AC 327 ms 47616 KB
subtask_01_22.txt AC 324 ms 47688 KB
subtask_01_23.txt AC 291 ms 47692 KB
subtask_01_24.txt AC 289 ms 47860 KB
subtask_01_25.txt AC 325 ms 47640 KB
subtask_01_26.txt AC 328 ms 47756 KB
subtask_01_27.txt AC 289 ms 47856 KB
subtask_01_28.txt AC 290 ms 47796 KB
subtask_01_29.txt AC 325 ms 47748 KB
subtask_01_30.txt AC 331 ms 47680 KB
subtask_01_31.txt AC 288 ms 47632 KB
subtask_01_32.txt AC 285 ms 47696 KB
subtask_01_33.txt AC 324 ms 47608 KB
subtask_01_34.txt AC 321 ms 47756 KB