#include <bits/stdc++.h>
#include "Encoder.h"
const int MAX = 5e5;
using namespace std;
vector<int> adj[MAX], seq;
long long st[MAX], en[MAX], T;
const int L = 250000 + 1;
const double app = 1.0556451;
void build()
{
seq.push_back(0);
for (int i = 0; i < 256; ++i)
{
int x = seq.back();
x = x * app;
if (x == seq.back())
++x;
seq.push_back(x);
}
}
void dfs(int x, int p)
{
st[x] = ++T;
for (auto u : adj[x])
{
if (u == p)
continue;
dfs(u, x);
}
int lo = 0, hi = (int)seq.size(), ans = 0;
while (lo <= hi)
{
int mid = (lo + hi) >> 1;
if (st[x] + seq[mid] >= T)
ans = mid, hi = mid - 1;
else
lo = mid + 1;
}
T = st[x] + seq[ans];
long long a = st[x] - 1, b = ans;
Code(x, a + (1ll << 20) * b);
}
void Encode(int N, int A[], int B[])
{
build();
for (int i = 0; i < N - 1; ++i)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(0, 0);
}
#include <bits/stdc++.h>
#include "Device.h"
using namespace std ;
vector<int> seq;
const int L = 250000 + 1;
const double app = 1.0556451;
void build()
{
seq.push_back(0);
for (int i = 0; i < 256; ++i)
{
int x = seq.back();
x = x * app;
if (x == seq.back())
++x;
seq.push_back(x);
}
}
void InitDevice()
{
build();
}
void adjust(long long x, long long &a, long long &b)
{
a = x & ((1 << 20) - 1);
x /= (1 << 20);
b = a + seq[x];
}
int Answer(long long S, long long T)
{
long long s1, t1;
long long s2, t2;
adjust(S, s1, t1);
adjust(T, s2, t2);
if (s2 >= s1 && t2 <= t1)
return 1;
if (s1 >= s2 && t1 <= t2)
return 0;
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12752 KB |
Output is correct |
2 |
Correct |
9 ms |
12516 KB |
Output is correct |
3 |
Correct |
9 ms |
12756 KB |
Output is correct |
4 |
Correct |
8 ms |
12644 KB |
Output is correct |
5 |
Correct |
9 ms |
12784 KB |
Output is correct |
6 |
Correct |
9 ms |
12784 KB |
Output is correct |
7 |
Correct |
9 ms |
12748 KB |
Output is correct |
8 |
Correct |
8 ms |
12744 KB |
Output is correct |
9 |
Correct |
9 ms |
12644 KB |
Output is correct |
10 |
Correct |
8 ms |
12644 KB |
Output is correct |
11 |
Correct |
9 ms |
12804 KB |
Output is correct |
12 |
Correct |
8 ms |
12516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
21296 KB |
Output is correct - L = 101711872 |
2 |
Correct |
200 ms |
21220 KB |
Output is correct - L = 101711872 |
3 |
Correct |
198 ms |
21396 KB |
Output is correct - L = 100663296 |
4 |
Correct |
203 ms |
21208 KB |
Output is correct - L = 101711872 |
5 |
Correct |
525 ms |
45488 KB |
Output is correct - L = 218103808 |
6 |
Correct |
524 ms |
45488 KB |
Output is correct - L = 218103808 |
7 |
Correct |
523 ms |
45632 KB |
Output is correct - L = 219152384 |
8 |
Correct |
537 ms |
45284 KB |
Output is correct - L = 218103808 |
9 |
Correct |
450 ms |
46220 KB |
Output is correct - L = 229638144 |
10 |
Correct |
441 ms |
46160 KB |
Output is correct - L = 231735296 |
11 |
Correct |
442 ms |
46044 KB |
Output is correct - L = 231735296 |
12 |
Correct |
440 ms |
46088 KB |
Output is correct - L = 231735296 |
13 |
Correct |
484 ms |
45848 KB |
Output is correct - L = 223346688 |
14 |
Correct |
516 ms |
45844 KB |
Output is correct - L = 220200960 |
15 |
Correct |
200 ms |
21192 KB |
Output is correct - L = 101711872 |
16 |
Correct |
199 ms |
21220 KB |
Output is correct - L = 101711872 |
17 |
Correct |
200 ms |
21144 KB |
Output is correct - L = 100663296 |
18 |
Correct |
495 ms |
45536 KB |
Output is correct - L = 230686720 |
19 |
Correct |
490 ms |
45808 KB |
Output is correct - L = 230686720 |
20 |
Correct |
484 ms |
45488 KB |
Output is correct - L = 230686720 |
21 |
Correct |
501 ms |
45356 KB |
Output is correct - L = 230686720 |
22 |
Correct |
507 ms |
45680 KB |
Output is correct - L = 230686720 |
23 |
Correct |
506 ms |
45360 KB |
Output is correct - L = 230686720 |
24 |
Correct |
506 ms |
45416 KB |
Output is correct - L = 229638144 |
25 |
Correct |
515 ms |
45364 KB |
Output is correct - L = 228589568 |
26 |
Correct |
536 ms |
45480 KB |
Output is correct - L = 227540992 |
27 |
Correct |
527 ms |
45408 KB |
Output is correct - L = 226492416 |