# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1224704 | mychecksedad | City (JOI17_city) | C++20 | 0 ms | 0 KiB |
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const ll N = 250000, M = 1e5+10, K = 52, MX = 30;
const double rt = 1.05;
int ww = 19;
vector<ll> W;
ll timer = 0, tin[N], tout[N], sum = 0, dep[N];
vi g[N];
void dfs(int v, int p){
tin[v] = timer++;
for(int u: g[v]){
if(u != p) dfs(u, v);
}
tout[v] = tin[v] + (*lower_bound(all(W), timer - tin[v]));
}
void initW(){
ll w = 1;
W.pb(w);
while(ww){
ll nw = floor((double)w * rt);
if(nw == w) ++nw;
if(nw > N) --ww;
W.pb(nw);
w = nw;
}
}
void code(int i, ll x){
Code(i, x);
}
void Encode(int n, int A[], int B[])
{
initW();
for(int i = 0; i + 1 < n; ++i){
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
dfs(0, 0);
ll ws = W.size();
for(int i = 0; i < n; ++i){
code(i, tin[i] * ws + (tout[i] - tin[i]));
}
}
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const ll N = 250000, M = 1e5+10, K = 52, MX = 30;
const double rtt = 1.05;
int www = 19;
vector<ll> WW;
ll wss;
void initWW(){
ll w = 1;
WW.pb(w);
while(www){
ll nw = floor((double)w * rtt);
if(nw == w) ++nw;
if(nw > N) --www;
WW.pb(nw);
w = nw;
}
}
void InitDevice()
{
initWW();
wss = WW.size();
}
bool is_ancestor(array<ll, 2> u, array<ll, 2> v){
return u[0] <= v[0] && v[1] <= u[1];
}
int Answer(long long S, long long T)
{
array<ll, 2> u = {S / wss, S / wss + WW[S % wss]};
array<ll, 2> v = {T / wss, T / wss + WW[T % wss]};
if(is_ancestor(u, v)) return 1;
if(is_ancestor(v, u)) return 0;
return 2;
}