Submission #1696560


Source Code Expand

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
// lca根つき木の2点間をO(log n)で
// 準備にはO(nlog n)
// 使い方
// 辺の情報入れる->root = 1 -> init(V+1)
const int MAX_LOG = 20;
vector<vector<int> > G(100005);
int root; // 根
int parent[MAX_LOG][100005];
int depth[100005];
void dfs(int v, int par, int d) {
  parent[0][v] = par;
  depth[v] = d;
  for(auto &to : G[v]) {
    if(to == par) continue;
    dfs(to, v, d + 1);
  }
}
void init(int V) {
  dfs(root, -1, 0);
  // parentを初期化する
  FOR(k,0,MAX_LOG-1) {
    FOR(v,0,V) {
      if(parent[k][v] < 0) parent[k+1][v] = -1;
      else parent[k+1][v] = parent[k][parent[k][v]];
    }
  }
}
// uとvのLCA(初めて出会う頂点番号)を求める
int lca(int u, int v) {
  // vの方が深いことにする
  if(depth[u] > depth[v]) swap(u, v);
  FOR(k,0,MAX_LOG) {
    if(((depth[v]-depth[u])>>k)&1) {
      v = parent[k][v];
    }
  }
  if(u == v) return u;
  // 二分探索
  for(int k = MAX_LOG - 1; k >= 0; k--) {
    if(parent[k][u] != parent[k][v]) {
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  FOR(i,0,N-1) {
    int x, y; cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  root = 1;
  init(N+1);
  int Q; cin >> Q;
  FOR(i,0,Q) {
    int a, b; cin >> a >> b;
    cout << depth[a] + depth[b] - 2 * depth[lca(a, b)] + 1 << endl;
  }
  return 0;
}


Submission Info

Submission Time
Task D - 閉路
User nenuon
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1925 Byte
Status AC
Exec Time 312 ms
Memory 19328 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 12
AC × 27
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 5 ms 8832 KB
subtask0_sample02.txt AC 5 ms 8832 KB
subtask0_sample03.txt AC 5 ms 8832 KB
subtask1_01.txt AC 36 ms 18688 KB
subtask1_02.txt AC 36 ms 18688 KB
subtask1_03.txt AC 5 ms 8832 KB
subtask1_04.txt AC 5 ms 8832 KB
subtask1_05.txt AC 5 ms 8832 KB
subtask1_06.txt AC 5 ms 8832 KB
subtask1_07.txt AC 50 ms 14080 KB
subtask1_08.txt AC 42 ms 13952 KB
subtask1_09.txt AC 53 ms 13952 KB
subtask1_10.txt AC 48 ms 13952 KB
subtask1_11.txt AC 47 ms 13952 KB
subtask1_12.txt AC 50 ms 13952 KB
subtask2_01.txt AC 215 ms 19328 KB
subtask2_02.txt AC 220 ms 19200 KB
subtask2_03.txt AC 186 ms 8960 KB
subtask2_04.txt AC 195 ms 8960 KB
subtask2_05.txt AC 201 ms 9088 KB
subtask2_06.txt AC 202 ms 9216 KB
subtask2_07.txt AC 283 ms 14336 KB
subtask2_08.txt AC 284 ms 14336 KB
subtask2_09.txt AC 293 ms 14336 KB
subtask2_10.txt AC 293 ms 14336 KB
subtask2_11.txt AC 312 ms 14336 KB
subtask2_12.txt AC 297 ms 14336 KB