#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 250'000 + 5;
vector<int> ad[mxN];
int timer;
int in[mxN], sz[mxN], out[mxN];
void dfs(int u, int p) {
in[u] = ++timer;
sz[u] = 1;
for (int v : ad[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
int val = 1, power = 0;
while (val < sz[u]) {
val = max(val + 1, (int) ceil((double) 1.05 * val));
power++;
}
timer += val - sz[u];
sz[u] = val;
out[u] = power;
}
void Encode(int N, int A[], int B[]) {
for (int i = 0; i < N - 1; i++) {
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
dfs(0, -1);
for (int i = 0; i < N; ++i) {
Code(i, in[i] * 256 + out[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice() {
}
int get(int x) {
int val = 1;
for (int i = 0; i < x; i++) val = max(val + 1, (int) ceil((double) 1.05 * val));
return val;
}
int Answer(long long S, long long T) {
int inS = S / 256, inT = T / 256;
int outS = inS + get(S % 256), outT = inT + get(T % 256);
if (inT <= inS && outT >= outS) return 0;
if (inS <= inT && outS >= outT) return 1;
return 2;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
15120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15120 KB |
Output is correct |
| 3 |
Correct |
2 ms |
15216 KB |
Output is correct |
| 4 |
Correct |
3 ms |
15120 KB |
Output is correct |
| 5 |
Correct |
3 ms |
15132 KB |
Output is correct |
| 6 |
Correct |
2 ms |
15132 KB |
Output is correct |
| 7 |
Correct |
2 ms |
15132 KB |
Output is correct |
| 8 |
Correct |
2 ms |
15132 KB |
Output is correct |
| 9 |
Correct |
2 ms |
15116 KB |
Output is correct |
| 10 |
Correct |
3 ms |
15132 KB |
Output is correct |
| 11 |
Correct |
2 ms |
15132 KB |
Output is correct |
| 12 |
Correct |
3 ms |
15132 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
157 ms |
22600 KB |
Output is correct - L = 194304 |
| 2 |
Correct |
144 ms |
22672 KB |
Output is correct - L = 196096 |
| 3 |
Correct |
145 ms |
22736 KB |
Output is correct - L = 190208 |
| 4 |
Correct |
148 ms |
22580 KB |
Output is correct - L = 195328 |
| 5 |
Correct |
449 ms |
40084 KB |
Output is correct - L = 78027264 |
| 6 |
Correct |
447 ms |
40156 KB |
Output is correct - L = 77611776 |
| 7 |
Correct |
462 ms |
40032 KB |
Output is correct - L = 78339584 |
| 8 |
Correct |
441 ms |
39696 KB |
Output is correct - L = 89339648 |
| 9 |
Correct |
574 ms |
47420 KB |
Output is correct - L = 127487232 |
| 10 |
Correct |
563 ms |
54608 KB |
Output is correct - L = 126131456 |
| 11 |
Correct |
555 ms |
54404 KB |
Output is correct - L = 145966592 |
| 12 |
Correct |
552 ms |
54560 KB |
Output is correct - L = 132397312 |
| 13 |
Correct |
509 ms |
54272 KB |
Output is correct - L = 102262528 |
| 14 |
Correct |
492 ms |
53784 KB |
Output is correct - L = 83629824 |
| 15 |
Correct |
145 ms |
29648 KB |
Output is correct - L = 200448 |
| 16 |
Correct |
150 ms |
29832 KB |
Output is correct - L = 205056 |
| 17 |
Correct |
145 ms |
30024 KB |
Output is correct - L = 185344 |
| 18 |
Correct |
569 ms |
53728 KB |
Output is correct - L = 139016192 |
| 19 |
Correct |
568 ms |
53724 KB |
Output is correct - L = 64000000 |
| 20 |
Correct |
565 ms |
53788 KB |
Output is correct - L = 64000000 |
| 21 |
Correct |
558 ms |
53692 KB |
Output is correct - L = 132397056 |
| 22 |
Correct |
568 ms |
53652 KB |
Output is correct - L = 64458240 |
| 23 |
Correct |
582 ms |
53576 KB |
Output is correct - L = 64631040 |
| 24 |
Correct |
579 ms |
53764 KB |
Output is correct - L = 65624320 |
| 25 |
Correct |
552 ms |
53436 KB |
Output is correct - L = 65913088 |
| 26 |
Correct |
556 ms |
53412 KB |
Output is correct - L = 66728704 |
| 27 |
Correct |
553 ms |
53428 KB |
Output is correct - L = 66947840 |
