Submission #4643639


Source Code Expand

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int root;
vector<int> g[100001];
int parent[17][20001];#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int root;
vector<int> g[100001];
int parent[17][100001];
int depth[100001];

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

void init(int V){
    dfs(root,-1,0);
    for(int i=0;i+1<17;i++){
        for(int j=1;j<=V;j++){
            if(parent[i][j]<0){
                parent[i+1][j]=-1;
            }
            else{
                parent[i+1][j]=parent[i][parent[i][j]];
            }
        }
    }
}

int lca(int x,int y){
    if(depth[x]>depth[y]){
        swap(x,y);
    }
    for(int i=0;i<17;i++){
        if((depth[y]-depth[x]) >> i&1){
            y=parent[i][y];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=16;i>=0;i--){
        if(parent[i][x]!=parent[i][y]){
            x=parent[i][x];
            y=parent[i][y];
        }
    }
    return parent[0][x];
}

int main(){
    int n,x,y,q,z;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    root=1;
    init(n);
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        scanf("%d %d",&x,&y);
        z=lca(x,y);
        printf("%d\n",1+depth[x]+depth[y]-2*depth[z]);
    }
}
int depth[100001];

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

void init(int V){
    dfs(root,-1,0);
    for(int i=0;i+1<17;i++){
        for(int j=1;j<=V;j++){
            if(parent[i][j]<0){
                parent[i+1][j]=-1;
            }
            else{
                parent[i+1][j]=parent[i][parent[i][j]];
            }
        }
    }
}

int lca(int x,int y){
    if(depth[x]>depth[y]){
        swap(x,y);
    }
    for(int i=0;i<17;i++){
        if((depth[y]-depth[x]) >> i&1){
            y=parent[i][y];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=16;i>=0;i--){
        if(parent[i][x]!=parent[i][y]){
            x=parent[i][x];
            y=parent[i][y];
        }
    }
    return parent[0][x];
}

int main(){
    int n,x,y,q,z;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    root=1;
    init(n);
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        scanf("%d %d",&x,&y);
        z=lca(x,y);
        printf("%d\n",1+depth[x]+depth[y]-2*depth[z]);
    }
}

Submission Info

Submission Time
Task D - 閉路
User AC961009
Language C++14 (Clang 3.8.0)
Score 0
Code Size 2853 Byte
Status CE

Compile Error

./Main.cpp:7:23: error: expected unqualified-id
int parent[17][20001];#include<cstdio>
                      ^
./Main.cpp:11:5: error: redefinition of 'root'
int root;
    ^
./Main.cpp:5:5: note: previous definition is here
int root;
    ^
./Main.cpp:12:13: error: redefinition of 'g'
vector<int> g[100001];
            ^
./Main.cpp:6:13: note: previous definition is here
vector<int> g[100001];
            ^
./Main.cpp:13:5: error: redefinition of 'parent' with a different type: 'int [17][100001]' vs 'int [17][20001]'
int parent[17][100001];
    ^
./Main.cpp:7:5: note: previous definition is here
int parent[17][20001];#include<cstdio>
    ^
./Main.cpp:78:5: error: redefinition of 'depth'
int depth[100001];
    ^
./Main.cpp:14:5: note: previous definition is here
int depth[100001];
    ^
./Main.cpp:80:6: error: redefinition of 'dfs'
void dfs(int v,int p,int d){
     ^
./Main.cpp:16:6: note: previous definition is here
void dfs(int v,int p,int d){
     ^
./Main.cpp:90:6: error: redefinition of 'init'
void init(in...