| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115615 |
2019-06-08T10:40:53 Z |
김세빈(#2868) |
Treasure Hunt (CEOI11_tre) |
C++14 |
|
714 ms |
60196 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[l1][i]; p1 = P[p1][i];
l2 = L[l2][i]; p2 = P[p2][i];
}
}
l1 = L[l1][0]; p1 = P[p1][0];
l2 = L[l2][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);
~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
497 ms |
60196 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
504 ms |
9848 KB |
Output is correct |
| 2 |
Incorrect |
334 ms |
39272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
491 ms |
39272 KB |
Output is correct |
| 2 |
Incorrect |
386 ms |
6052 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
714 ms |
39316 KB |
Output is correct |
| 2 |
Runtime error |
8 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
3856 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
548 ms |
39300 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
572 ms |
39404 KB |
Output isn't correct |
