Submission #1612427


Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cassert>
#include <cstring>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

struct LCA {
    int max_iter, root = 0;
    vector<vector<int>> edge;
    vector<vector<int>> parent;
    vector<int> depth;

    LCA(int n) : edge(n), depth(n) {
        max_iter = log(n) / log(2) + 1;
        parent.resize(max_iter,vector<int>(n));
    }

    void add_edge(int u, int v) {
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    void dfs(int u, int p, int d) {
        static vector<bool> used(edge.size());
        used[u] = true;
        parent[0][u] = p;
        depth[u] = d;
        for (auto v: edge[u]) if (!used[v]) {
            dfs(v,u,d+1);
        }
    }

    void preprocess() {
        dfs(root,root,0);
        for (int i = 0; i < max_iter-1; i++) {
            for (int j = 0; j < edge.size(); j++) {
                parent[i+1][j] = parent[i][parent[i][j]];
            }
        }
    }

    int pathlen(int u, int v) {
        int p = get(u,v);
        return depth[u] + depth[v] - 2 * depth[p];
    }

    int get(int u, int v) {
        if (depth[u] < depth[v]) swap(u,v);
        for (int i = 0; i < max_iter; i++) {
            if (1<<i & (depth[u] - depth[v])) {
                u = parent[i][u];
            }
        }
        if (u == v) return u;
        for (int i = max_iter-1; i >= 0; i--) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        assert(parent[0][u] == parent[0][v]);
        return parent[0][u];
    }
};

int main(void) {
    int i, n;
    scanf("%d",&n);

    LCA lca(n);
    REP (i,n-1) {
        int x, y;
        scanf("%d%d",&x,&y);
        x--; y--;
        lca.add_edge(x,y);
    }
    lca.preprocess();

    int q;
    scanf("%d",&q);
    while (q--) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--; b--;
        printf("%d\n",lca.pathlen(a,b) + 1);
    }
    return 0;
}

Submission Info

Submission Time
Task D - 閉路
User h_noson
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2556 Byte
Status AC
Exec Time 135 ms
Memory 17784 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:88:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^
./Main.cpp:95:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
./Main.cpp:98:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

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 3 ms 512 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask1_01.txt AC 37 ms 17016 KB
subtask1_02.txt AC 37 ms 17016 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 384 KB
subtask1_06.txt AC 1 ms 384 KB
subtask1_07.txt AC 44 ms 12920 KB
subtask1_08.txt AC 49 ms 12792 KB
subtask1_09.txt AC 49 ms 12792 KB
subtask1_10.txt AC 49 ms 12792 KB
subtask1_11.txt AC 45 ms 12792 KB
subtask1_12.txt AC 45 ms 12792 KB
subtask2_01.txt AC 65 ms 17784 KB
subtask2_02.txt AC 65 ms 17656 KB
subtask2_03.txt AC 25 ms 384 KB
subtask2_04.txt AC 28 ms 512 KB
subtask2_05.txt AC 34 ms 640 KB
subtask2_06.txt AC 35 ms 768 KB
subtask2_07.txt AC 115 ms 13176 KB
subtask2_08.txt AC 124 ms 13176 KB
subtask2_09.txt AC 118 ms 13432 KB
subtask2_10.txt AC 135 ms 13176 KB
subtask2_11.txt AC 133 ms 13176 KB
subtask2_12.txt AC 132 ms 13176 KB