Submission #604512
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
/******************************
LCA.cpp START
******************************/
/******************************
Lowest Common Ancestor
木において最も近い共通祖先を求める
******************************/
//SETTING
//型設定(int?long?ll?)
typedef int lca_t;
//ノードの個数
const lca_t MAX_V = 100000;
//ダブリングに必要なサイズ(log(MAX_V))
const lca_t MAX_LOG_V = 20;
//木の隣接リスト表現
vector<lca_t> G[MAX_V];
//根のノード番号
lca_t root = 0;
//親を2^k回辿って到達するノード(根を通り過ぎる場合,-1)
int parent[MAX_LOG_V][MAX_V];
//根からの深さ
int depth[MAX_V];
//現在vに注目、親はp、深さd
void lca_dfs(lca_t v, lca_t p, lca_t d){
parent[0][v]=p;
depth[v]=d;
for(lca_t i=0; i<G[v].size(); ++i){
if(G[v][i]!=p){ //親でなければ子
lca_dfs(G[v][i], v, d+1);
}
}
}
//初期化
void lca_init(lca_t V){
//parent[0]とdepthの初期化
lca_dfs(root, -1, 0);
//parentの初期化
for(lca_t k=0; k+1<MAX_LOG_V; ++k){
for(lca_t 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]];
}
}
}
//uとvのLCAを求める
lca_t lca(lca_t u, lca_t v){
//uとvの深さが同じになるまで親を辿る
if(depth[u] > depth[v]) swap(u,v);
for(lca_t k=0; k<MAX_LOG_V; ++k){
if((depth[v]-depth[u])>>k & 1){
v = parent[k][v];
}
}
if(u==v) return u;
//二分探索でLCAを求める
for(lca_t k=MAX_LOG_V-1; k>=0; --k){
if(parent[k][u] != parent[k][v]){
u=parent[k][u];
v=parent[k][v];
}
}
return parent[0][u];
}
/******************************
LCA.cpp END
******************************/
int main(){
int n;
cin >>n;
for(int i=0; i<n-1; ++i){
int x, y;
scanf(" %d %d", &x, &y);
--x;
--y;
G[x].push_back(y);
G[y].push_back(x);
}
//LCA初期設定
lca_init(n);
int q;
cin >> q;
for(int Q=0; Q<q; ++Q){
int a,b;
scanf(" %d %d", &a, &b);
--a;
--b;
printf("%d\n", depth[a]+depth[b]+1-2*depth[lca(a,b)]);
}
}
Submission Info
Submission Time
2016-01-06 00:28:09+0900
Task
D - 閉路
User
imulan
Language
C++ (G++ 4.6.4)
Score
100
Code Size
2720 Byte
Status
AC
Exec Time
261 ms
Memory
19116 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:112:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:126:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
Sample
Subtask1
Subtask2
Score / Max Score
0 / 0
30 / 30
70 / 70
Status
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
30 ms
3232 KB
subtask0_sample02.txt
AC
27 ms
3108 KB
subtask0_sample03.txt
AC
27 ms
3112 KB
subtask1_01.txt
AC
104 ms
19116 KB
subtask1_02.txt
AC
106 ms
19112 KB
subtask1_03.txt
AC
28 ms
3228 KB
subtask1_04.txt
AC
28 ms
3232 KB
subtask1_05.txt
AC
38 ms
3228 KB
subtask1_06.txt
AC
29 ms
3356 KB
subtask1_07.txt
AC
114 ms
14504 KB
subtask1_08.txt
AC
114 ms
14508 KB
subtask1_09.txt
AC
120 ms
14496 KB
subtask1_10.txt
AC
122 ms
14436 KB
subtask1_11.txt
AC
116 ms
14500 KB
subtask1_12.txt
AC
116 ms
14500 KB
subtask2_01.txt
AC
165 ms
19112 KB
subtask2_02.txt
AC
162 ms
19108 KB
subtask2_03.txt
AC
81 ms
3228 KB
subtask2_04.txt
AC
87 ms
3356 KB
subtask2_05.txt
AC
104 ms
3240 KB
subtask2_06.txt
AC
95 ms
3232 KB
subtask2_07.txt
AC
236 ms
14496 KB
subtask2_08.txt
AC
243 ms
14496 KB
subtask2_09.txt
AC
251 ms
14496 KB
subtask2_10.txt
AC
258 ms
14500 KB
subtask2_11.txt
AC
261 ms
14500 KB
subtask2_12.txt
AC
256 ms
14496 KB