Submission #1956420


Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_V = 100000;
const int MAX_LOG_V = (int)log2(MAX_V);

const int MAX_Q = 100000;

//vector<int> G[MAX_V]
array<vector<int>, MAX_V> G;     // グラフの隣接リスト表現
int root;                        // 根ノードの番号

// 親を 2^k 回辿って到達する頂点(根を通りすぎる場合は -1 とする)
// int parent[MAX_LOG_V][MAX_V]
vector< vector<int> > parent(MAX_V, vector<int>(MAX_LOG_V, -1));

// 根からの深さ
// int depth[MAX_V]
array<int, MAX_V> depth;

// q[MAX_Q][2]
array<array<int, 2>, MAX_Q> q;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

void dfs(int v, int p, int d)
{
    parent[0][v] = p;
    depth[v] = d;
    for (int i = 0; i < (signed)G[v].size(); i++)
        if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}

// 初期化
void init(int V)
{
    // parent[0] と depth を初期化する
    dfs(root, -1, 0);
    // parent を初期化する
    for (int k = 0; k + 1 < MAX_LOG_V; k++)
        for (int v = 0; v < V; 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)
{
    // u と v の深さが同じになるまで親を辿る
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < MAX_LOG_V; k++)
        if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
    if (u == v) return u;
    // 二分探索で LCA を求める
    for (int k = MAX_LOG_V - 1; 0 <= k; k--)
        if (parent[k][u] != parent[k][v])
        {
            u = parent[k][u];
            v = parent[k][v];
        }
    return parent[0][u];
}

int main()
{
    int N;
    gc(N);

    for (int i = 0; i < N - 1; i++)
    {
        int x, y;
        gc(x);
        gc(y);

        G[min(x, y) - 1].push_back(max(x, y) - 1);
    }

    int Q;
    gc(Q);

    root = 0;
    init(N);

    for (int i = 0; i < Q; i++)
    {
        int a, b;
        gc(a);
        gc(b);

        int l = lca(a - 1, b - 1);
        printf("%d\n",
            depth[a - 1] + depth[b - 1] - 2 * depth[l] + 1);
    }

    return 0;
}

Submission Info

Submission Time
Task D - 閉路
User ShinjiSHIBATA
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2645 Byte
Status RE
Exec Time 137 ms
Memory 23040 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
WA × 1
RE × 11
AC × 3
WA × 2
RE × 22
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 10 ms 12800 KB
subtask0_sample02.txt AC 11 ms 12672 KB
subtask0_sample03.txt AC 11 ms 12672 KB
subtask1_01.txt RE 126 ms 22528 KB
subtask1_02.txt RE 117 ms 22528 KB
subtask1_03.txt WA 10 ms 12800 KB
subtask1_04.txt RE 107 ms 12800 KB
subtask1_05.txt RE 106 ms 12800 KB
subtask1_06.txt RE 106 ms 12800 KB
subtask1_07.txt RE 116 ms 14720 KB
subtask1_08.txt RE 119 ms 14720 KB
subtask1_09.txt RE 116 ms 14720 KB
subtask1_10.txt RE 118 ms 14720 KB
subtask1_11.txt RE 117 ms 14720 KB
subtask1_12.txt RE 120 ms 14720 KB
subtask2_01.txt RE 132 ms 23040 KB
subtask2_02.txt RE 134 ms 23040 KB
subtask2_03.txt WA 25 ms 12928 KB
subtask2_04.txt RE 121 ms 12928 KB
subtask2_05.txt RE 121 ms 12928 KB
subtask2_06.txt RE 121 ms 12928 KB
subtask2_07.txt RE 135 ms 14848 KB
subtask2_08.txt RE 134 ms 14976 KB
subtask2_09.txt RE 134 ms 14976 KB
subtask2_10.txt RE 137 ms 14976 KB
subtask2_11.txt RE 135 ms 14976 KB
subtask2_12.txt RE 135 ms 14976 KB