Submission #1595185


Source Code Expand

#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;


struct LCA{
    static const int MAX_LOG = 20;
    const int V;
    int root;
    vector<vector<int>> es, parent;
    vector<int> depth;
    LCA(int V, int root) : V(V), es(V), parent(MAX_LOG, vector<int>(V)), depth(V), root(root){}
    void add_edge(int a, int b) {
        es[a].pb(b);
        es[b].pb(a);
    }
    void dfs(int cur, int par, int d) {
        parent[0][cur] = par;
        depth[cur] = d;
        for(auto& to: es[cur]) if(to != par) {
            dfs(to, cur, d+1);
        }
    }
    void init(){
        dfs(root, -1, 0);
        for(int k = 0; k+1 < MAX_LOG; ++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]];
            }
        }
    }
    int lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        for(int k = 0; k < MAX_LOG; ++k) {
            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 dist(int u, int v) {
        return depth[u] + depth[v] - 2*depth[lca(u, v)];
    }
};

int main(){
#ifdef LOCAL_TEST
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n;
    cin >> n;
    LCA g(n, 0);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        g.add_edge(--a, --b);
    }
    g.init();
    int q;
    cin >> q;
    rep(i, q) {
        int a, b;
        cin >> a >> b;
        cout << g.dist(--a, --b) + 1 << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - 閉路
User T1610
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2400 Byte
Status AC
Exec Time 384 ms
Memory 17528 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 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask1_01.txt AC 75 ms 16888 KB
subtask1_02.txt AC 75 ms 16888 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 2 ms 384 KB
subtask1_06.txt AC 2 ms 384 KB
subtask1_07.txt AC 85 ms 14072 KB
subtask1_08.txt AC 85 ms 13944 KB
subtask1_09.txt AC 85 ms 14072 KB
subtask1_10.txt AC 85 ms 13944 KB
subtask1_11.txt AC 82 ms 13944 KB
subtask1_12.txt AC 81 ms 13944 KB
subtask2_01.txt AC 293 ms 17528 KB
subtask2_02.txt AC 292 ms 17528 KB
subtask2_03.txt AC 208 ms 384 KB
subtask2_04.txt AC 211 ms 512 KB
subtask2_05.txt AC 225 ms 640 KB
subtask2_06.txt AC 223 ms 768 KB
subtask2_07.txt AC 362 ms 14328 KB
subtask2_08.txt AC 360 ms 14328 KB
subtask2_09.txt AC 384 ms 14328 KB
subtask2_10.txt AC 375 ms 14328 KB
subtask2_11.txt AC 378 ms 14328 KB
subtask2_12.txt AC 382 ms 14328 KB