Submission #1519495


Source Code Expand

#include <iostream>
#include <vector>
#define N 100000
#define L 17
using namespace std;
vector<int> g[N];
int d[N]={},p[L][N]={{}};
void f(int i){
    for(int j=0;j<g[i].size();j++){
        if(g[i][j]==p[0][i]) 
            continue;
        p[0][g[i][j]]=i;
        d[g[i][j]]=d[i]+1;
        f(g[i][j]);
    }
}           
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x-1].push_back(y-1);
        g[y-1].push_back(x-1);
    }
    f(0);
    for(int i=1;i<L;i++){
        for(int j=0;j<n;j++)
            p[i][j]=p[i-1][p[i-1][j]];
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a;
        cin>>b;
        a--;
        b--;
        int r=d[a]+d[b]+1;
        if(d[a]<d[b])
            swap(a,b);
        for(int i=0;i<L;i++){
            if((d[a]-d[b])&(1<<i))
                a=p[i][a];
        }
        if(a!=b){
            for(int i=L-1;i>=0;i--){
                if(p[i][a]!=p[i][b]){
                    a=p[i][a];
                    b=p[i][b];
                }
            }
            a=p[0][a];
        }
        cout<<r-d[a]*2<<endl;
    }
}

Submission Info

Submission Time
Task D - 閉路
User hillpeople
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1215 Byte
Status AC
Exec Time 381 ms
Memory 18048 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 3 ms 7552 KB
subtask0_sample02.txt AC 3 ms 7552 KB
subtask0_sample03.txt AC 3 ms 7552 KB
subtask1_01.txt AC 88 ms 17408 KB
subtask1_02.txt AC 87 ms 17408 KB
subtask1_03.txt AC 3 ms 7552 KB
subtask1_04.txt AC 3 ms 7552 KB
subtask1_05.txt AC 4 ms 7680 KB
subtask1_06.txt AC 4 ms 7680 KB
subtask1_07.txt AC 103 ms 12800 KB
subtask1_08.txt AC 99 ms 12800 KB
subtask1_09.txt AC 95 ms 12800 KB
subtask1_10.txt AC 109 ms 12800 KB
subtask1_11.txt AC 98 ms 12800 KB
subtask1_12.txt AC 94 ms 12800 KB
subtask2_01.txt AC 320 ms 18048 KB
subtask2_02.txt AC 311 ms 18048 KB
subtask2_03.txt AC 201 ms 7808 KB
subtask2_04.txt AC 210 ms 7936 KB
subtask2_05.txt AC 225 ms 7936 KB
subtask2_06.txt AC 229 ms 8064 KB
subtask2_07.txt AC 351 ms 13184 KB
subtask2_08.txt AC 371 ms 13056 KB
subtask2_09.txt AC 351 ms 13056 KB
subtask2_10.txt AC 364 ms 13184 KB
subtask2_11.txt AC 381 ms 13184 KB
subtask2_12.txt AC 358 ms 13184 KB