#include "Encoder.h"
#include <vector>
using namespace std;
vector<int> edge[250000];
vector<int> range;
int in[250000],p[250000];
int cnt;
void dfs(int x,int from) {
in[x] =cnt++;
for (auto to : edge[x]) {
if (to == from) continue;
dfs(to, x);
}
if (in[x] == cnt - 1) return;
int &e=p[x];
while (in[x] + range[e] < cnt - 1) ++e;
cnt = in[x] + range[e] + 1;
}
void Encode(int N, int A[], int B[])
{
//const double r = 1.055645;
const double r = 1.026056;
range.push_back(0);
for (int i = 1;i<512; ++i) {
int ar = r * range.back();
if (range.back() == ar) ++ar;
range.push_back(ar);
}
for (int i = 0; i < N-1; ++i) {
edge[B[i]].push_back(A[i]);
edge[A[i]].push_back(B[i]);
}
dfs(0,-1);
for (int i = 0; i < N ; ++i)
Code(i, in[i] + (p[i] << 19));
}
#include "Device.h"
#include <vector>
using namespace std;
vector<int> a;
void InitDevice()
{
const double r = 1.026056;
a.push_back(0);
for (int i = 1; i < 512; ++i) {
int ar = a.back()*r;
if (a.back() == ar)++ar;
a.push_back(ar);
}
}
int Answer(long long S, long long T)
{
int ss = S & ((1 << 19) - 1);
int ts= T & ((1 << 19) - 1);
int se = ss+a[S >> 19];
int te = ts+a[T >> 19];
if (ss <= ts && te <= se) return 1;
if (ts <= ss && se <= te) return 0;
return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12424 KB |
Output is correct |
2 |
Correct |
11 ms |
12272 KB |
Output is correct |
3 |
Correct |
10 ms |
12272 KB |
Output is correct |
4 |
Correct |
9 ms |
12528 KB |
Output is correct |
5 |
Correct |
9 ms |
12272 KB |
Output is correct |
6 |
Correct |
11 ms |
12528 KB |
Output is correct |
7 |
Correct |
9 ms |
12016 KB |
Output is correct |
8 |
Correct |
11 ms |
12272 KB |
Output is correct |
9 |
Correct |
10 ms |
12272 KB |
Output is correct |
10 |
Correct |
9 ms |
12272 KB |
Output is correct |
11 |
Correct |
9 ms |
12272 KB |
Output is correct |
12 |
Correct |
9 ms |
12528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
24816 KB |
Output is correct - L = 90701824 |
2 |
Correct |
208 ms |
24880 KB |
Output is correct - L = 90701824 |
3 |
Correct |
202 ms |
25016 KB |
Output is correct - L = 90701824 |
4 |
Correct |
200 ms |
25072 KB |
Output is correct - L = 90701824 |
5 |
Correct |
506 ms |
60712 KB |
Output is correct - L = 212336640 |
6 |
Correct |
564 ms |
60488 KB |
Output is correct - L = 212860928 |
7 |
Correct |
536 ms |
60656 KB |
Output is correct - L = 212336640 |
8 |
Correct |
551 ms |
60400 KB |
Output is correct - L = 212860928 |
9 |
Correct |
445 ms |
61912 KB |
Output is correct - L = 218103808 |
10 |
Correct |
448 ms |
61912 KB |
Output is correct - L = 219676672 |
11 |
Correct |
446 ms |
61160 KB |
Output is correct - L = 219676672 |
12 |
Correct |
451 ms |
60544 KB |
Output is correct - L = 219676672 |
13 |
Correct |
485 ms |
61480 KB |
Output is correct - L = 215482368 |
14 |
Correct |
517 ms |
61000 KB |
Output is correct - L = 213385216 |
15 |
Correct |
200 ms |
24816 KB |
Output is correct - L = 90701824 |
16 |
Correct |
202 ms |
24816 KB |
Output is correct - L = 91226112 |
17 |
Correct |
200 ms |
24824 KB |
Output is correct - L = 90701824 |
18 |
Correct |
493 ms |
60888 KB |
Output is correct - L = 219152384 |
19 |
Correct |
498 ms |
61160 KB |
Output is correct - L = 219152384 |
20 |
Correct |
496 ms |
61200 KB |
Output is correct - L = 219152384 |
21 |
Correct |
492 ms |
60896 KB |
Output is correct - L = 218103808 |
22 |
Correct |
524 ms |
61048 KB |
Output is correct - L = 218628096 |
23 |
Correct |
544 ms |
61408 KB |
Output is correct - L = 218628096 |
24 |
Correct |
517 ms |
60912 KB |
Output is correct - L = 218628096 |
25 |
Correct |
517 ms |
60912 KB |
Output is correct - L = 217579520 |
26 |
Correct |
546 ms |
60656 KB |
Output is correct - L = 217579520 |
27 |
Correct |
549 ms |
60560 KB |
Output is correct - L = 216530944 |