oj.uz

답안 #115616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115616 2019-06-08T10:49:39 Z 김세빈(#2868) Treasure Hunt (CEOI11_tre) C++14
100 / 100
 669 ms 74108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> V;
int P[404040][22], L[404040][22];
int D[404040], X[404040];
int n, k;

pii idx(int v)
{
	int p, l;
	
	p = lower_bound(V.begin(), V.end(), v) - V.begin();
	l = V[p] - v;
	
	return pii(p, l);
}

pii lca(int p1, int l1, int p2, int l2)
{
	int i;
	
	if(D[p1] < D[p2]){
		swap(p1, p2);
		swap(l1, l2);
	}
	
	for(i=0; i<19; i++){
		if(D[p2] - D[p1] & (1 << i)){
			l1 = L[p1][i];
			p1 = P[p1][i];
		}
	}
	
	if(p1 == p2) return pii(p1, max(l1, l2));
	
	for(i--; i>=0; i--){
		if(P[p1][i] != P[p2][i]){
			l1 = L[p1][i]; p1 = P[p1][i];
			l2 = L[p2][i]; p2 = P[p2][i];
		}
	}
	
	l1 = L[p1][0]; p1 = P[p1][0];
	l2 = L[p2][0]; p2 = P[p2][0];
	
	return pii(p1, max(l1, l2));
}

pii up(int p1, int l1, int x)
{
	int i, p2, l2;
	
	for(i=19; i>=0; i--){
		p2 = P[p1][i]; l2 = L[p1][i];
		if((X[p1] - l1) - (X[p2] - l2) <= x){
			x -= (X[p1] - l1) - (X[p2] - l2);
			p1 = p2; l1 = l2;
		}
	}
	
	return pii(p1, l1 + x);
}

void init()
{
	n = 1;
	V.push_back(1);
}

void path(int p, int s)
{
	int i, l;
	
	n += s; k ++;
	V.push_back(n);
	
	tie(p, l) = idx(p);
	P[k][0] = p; L[k][0] = l;
	D[k] = D[p] + 1;
	X[k] = X[p] - l + s;
	
	for(i=1; i<19; i++){
		L[k][i] = L[P[k][i - 1]][i - 1];
		P[k][i] = P[P[k][i - 1]][i - 1];
	}
}

int dig(int p1, int p2)
{
	int p, p3, l, l1, l2, l3, x1, x2;
	
	tie(p1, l1) = idx(p1);
	tie(p2, l2) = idx(p2);
	tie(p3, l3) = lca(p1, l1, p2, l2);
	
	x1 = (X[p1] - l1) - (X[p3] - l3);
	x2 = (X[p2] - l2) - (X[p3] - l3);
	
	if(x1 > x2) tie(p, l) = up(p1, l1, x1 + x2 >> 1);
	else tie(p, l) = up(p2, l2, x1 + x2 + 1 >> 1);
	
	return V[p] - l;
}

Compilation message

tre.cpp: In function 'pii lca(int, int, int, int)':
tre.cpp:32:12: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(D[p2] - D[p1] & (1 << i)){
      ~~~~~~^~~~~~~
tre.cpp: In function 'int dig(int, int)':
tre.cpp:103:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(x1 > x2) tie(p, l) = up(p1, l1, x1 + x2 >> 1);
                                     ~~~^~~~
tre.cpp:104:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else tie(p, l) = up(p2, l2, x1 + x2 + 1 >> 1);
                              ~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 888 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 60168 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 508 ms 9784 KB Output is correct
2 Correct 335 ms 39276 KB Output is correct
3 Correct 307 ms 39404 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 484 ms 39268 KB Output is correct
2 Correct 382 ms 6136 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 669 ms 39280 KB Output is correct
2 Correct 446 ms 39272 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 11160 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 39420 KB Output is correct
2 Correct 496 ms 74108 KB Output is correct
3 Correct 274 ms 74088 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 561 ms 39260 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 39404 KB Output is correct