AtCoder Beginner Contest 014

Submission #604512

Source codeソースコード

#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

Task問題 D - 閉路
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++ (G++ 4.6.4)
Status状態 AC
Score得点 100
Source lengthソースコード長 2720 Byte
File nameファイル名
Exec time実行時間 261 ms
Memory usageメモリ使用量 19116 KB

Compiler messageコンパイルメッセージ

./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]

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask1 30 / 30 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 70 / 70 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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