#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg=20;
int cur=2;
vector<ll>Dep, Upd(lg+1), Lvl;
vector<vector<ll> >Lca, Dis;
int find_lca(int u, int v){
// u
// v
if(Lvl[v]<Lvl[u])
swap(u, v);
for(int i=lg;i>=0;i--){
if(Lvl[Lca[v][i]]>Lvl[u])
v=Lca[v][i];
}
if(Lvl[u]!=Lvl[v])
v=Lca[v][0];
if(u==v)
return u;
for(int i=lg;i>=0;i--){
if(Lca[u][i]!=Lca[v][i])
u=Lca[u][i], v=Lca[v][i];
}
u=Lca[u][0], v=Lca[v][0];
return u;
}
void init(){
Dep.push_back(0);
Dep.push_back(0);
Lvl.push_back(0);
Lvl.push_back(0);
Lca.push_back(Upd);
Lca.push_back(Upd);
Dis.push_back(Upd);
Dis.push_back(Upd);
}
void path(int a, int s){
int u=cur++;
Dep.push_back(Dep[a]+s);
Lvl.push_back(Dep[a]+1);
Lca.push_back(Upd);
Dis.push_back(Upd);
Lca[u][0]=a;
for(int j=1;j<=lg;j++){
Lca[u][j]=Lca[Lca[u][j-1]][j-1];
Dis[u][j]=Dis[u][j-1]+Dis[Lca[u][j-1]][j-1];
}
}
int dig(int u, int v){
int lca=find_lca(u, v);
ll dis=Dep[u]+Dep[v]-Dep[lca];
ll travel=dis/2;
ll u_to_lca=0;
int real_u=u;
for(int j=lg;j>=0;j--){
if(Lvl[Lca[u][j]]>Lvl[lca])
u_to_lca+=Dis[u][j], u=Lca[u][j];
}
if(u!=lca)
u_to_lca+=Dis[u][0], u=Lca[u][0];
u=real_u;
ll real_dis=0;
if(u_to_lca>=travel){
for(int j=lg;j>=0;j--){
if(real_dis+Lca[u][j]<=travel)
real_dis+=Dis[u][j], u=Lca[u][j];
}
}
else{
swap(u, v);
for(int j=lg;j>=0;j--){
if(real_dis+Lca[u][j]<travel)
real_dis+=Dis[u][j], u=Lca[u][j];
}
u=Lca[u][0];
}
return u;
}
//int main()
//{
// int num_calls;
// scanf("%d", &num_calls);
// for (int i = 1; i <= num_calls; i++)
// {
// char call[2];
// int a, b;
// scanf("%s%d%d", call, &a, &b);
// if (call[0] == 'i')
// init();
// else if (call[0] == 'p')
// path(a, b);
// else
// printf("%d\n", dig(a, b));
// }
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
380 ms |
95704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
