Submission #4325911


Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

const int N_MAX = 100010;
const int MAX_LOG_V = 20;
vector<vector<ll> > G;

ll depth[N_MAX] = {};
ll parent[MAX_LOG_V][N_MAX] = {};

void dfs(ll index, ll prev, ll _depth){
    depth[index] = _depth;
    parent[0][index] = prev;

    auto list = G[index];
    for(ll to : list){
        if(to==prev){
            continue;
        }
        dfs(to, index, _depth+1);
    }
    return;
}

ll LCA(ll a, ll b){
    if(a==b){
        return a;
    }

    // aよりbが深い(または同じ)と仮定する
    if(depth[a] > depth[b]){
        swap(a, b);
    }
    
    // bを根側に辿っていく
    ll diff_depth = depth[b] - depth[a];
    FOR(k, 0, MAX_LOG_V){
        if(diff_depth >> k & 1){
            b = parent[k][b];
        }
    }

    // aとbの深さが揃った
    if(a==b){
        return a;
    }

    // 大きい歩幅で共通親までジャンプ
    for(int k=MAX_LOG_V-1; k>=0; k--){
        if(parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }

    // 1つ上がLCA
    return parent[0][a];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin >> N;
    G.resize(N+1);

    FOR(i, 0, N-1){
        ll x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1, -1, 0);

    // ダブリングで親 2^k
    FOR(k, 1, MAX_LOG_V){
        FOR(i, 1, N+1){
            ll p = parent[k-1][i];
            parent[k][i] = parent[k-1][p];
        }
    }

    ll Q;
    cin >> Q;
    
    FOR(i, 0, Q){
        ll a, b;
        cin >> a >> b;
    
        ll lca = LCA(a, b);
        ll dist0 = depth[a] - depth[lca];
        ll dist1 = depth[b] - depth[lca];
        ll L = dist0 + dist1 + 1;
        p(L);
    }
    
    return 0;
}

Submission Info

Submission Time
Task D - 閉路
User peroon
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2531 Byte
Status
Exec Time 358 ms
Memory 32256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 30 / 30 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 70 / 70 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 4 ms 14592 KB
subtask0_sample02.txt 4 ms 14592 KB
subtask0_sample03.txt 4 ms 14592 KB
subtask1_01.txt 41 ms 31488 KB
subtask1_02.txt 41 ms 31488 KB
subtask1_03.txt 4 ms 14592 KB
subtask1_04.txt 4 ms 14592 KB
subtask1_05.txt 4 ms 14720 KB
subtask1_06.txt 4 ms 14720 KB
subtask1_07.txt 49 ms 22784 KB
subtask1_08.txt 49 ms 22656 KB
subtask1_09.txt 50 ms 22656 KB
subtask1_10.txt 50 ms 22656 KB
subtask1_11.txt 49 ms 22656 KB
subtask1_12.txt 52 ms 22656 KB
subtask2_01.txt 212 ms 32256 KB
subtask2_02.txt 212 ms 32128 KB
subtask2_03.txt 181 ms 14848 KB
subtask2_04.txt 186 ms 14848 KB
subtask2_05.txt 196 ms 14976 KB
subtask2_06.txt 197 ms 15104 KB
subtask2_07.txt 293 ms 23040 KB
subtask2_08.txt 292 ms 22912 KB
subtask2_09.txt 358 ms 23040 KB
subtask2_10.txt 299 ms 23040 KB
subtask2_11.txt 277 ms 23040 KB
subtask2_12.txt 273 ms 23040 KB