#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
const int M = 850;
int n;
ll len[1024] = {0};
void init(){
for(int i=1; i<=M; i++){
len[i] = round(double(len[i-1]) * 1.05);
if(len[i] == len[i-1]) len[i]++;
}
}
vector<int> link[250005];
ll in[250005], out[250002], inCnt, t[250002];
void dfs(int x, int p=-1){
in[x] = ++inCnt;
for(int y: link[x]){
if(y==p) continue;
dfs(y, x);
}
t[x] = lower_bound(len, len+M+1, inCnt - in[x]) - len;
out[x] = in[x] + len[t[x]];
}
void encode(int N, int A[], int B[]){
init();
n = N;
for(int i=0; i<n-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
dfs(0);
for(int i=0; i<n; i++) Code(i, in[i] << 10 | t[i]);
}
}
void Encode(int N, int A[], int B[]){
encode(N, A, B);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
const int M = 850;
int len[1024] = {0};
void init(){
for(int i=1; i<=M; i++){
len[i] = round(double(len[i-1]) * 1.05);
if(len[i] == len[i-1]) len[i]++;
}
}
}
void InitDevice(){
init();
}
int Answer(ll S, ll T){
ll SL = S >> 10, SR = SL + len[S & 1023];
ll TL = T >> 10, TR = TL + len[T & 1023];
if(SL<=TL&&TR<=SR) return 1;
if(TL<=SL&&SR<=TR) return 0;
return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
13088 KB |
Output is correct |
2 |
Correct |
1 ms |
13088 KB |
Output is correct |
3 |
Correct |
1 ms |
13088 KB |
Output is correct |
4 |
Correct |
1 ms |
13088 KB |
Output is correct |
5 |
Correct |
1 ms |
13088 KB |
Output is correct |
6 |
Correct |
1 ms |
13088 KB |
Output is correct |
7 |
Correct |
2 ms |
13076 KB |
Output is correct |
8 |
Correct |
1 ms |
13088 KB |
Output is correct |
9 |
Correct |
2 ms |
13076 KB |
Output is correct |
10 |
Correct |
1 ms |
13072 KB |
Output is correct |
11 |
Correct |
1 ms |
13088 KB |
Output is correct |
12 |
Correct |
2 ms |
13088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
89 ms |
20644 KB |
Wrong Answer [6] |
2 |
Halted |
0 ms |
0 KB |
- |