#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400
namespace {
ll opof[MAX]; //onepointofive
vector<ll> adj[303030];
ll ord[303030];
ll num[303030];
ll tnum[303030];
ll cnt = 0;
}
ll dfs(ll x, ll p = -1) {
num[x] = 1;
ord[x] = ++cnt;
ll sum = 0;
for (auto v : adj[x]) {
if (v == p) continue;
ll res = dfs(v, x);
num[x] += res;
sum += res;
cnt = ord[x] + sum;
}
tnum[x] = lower_bound(opof, opof + MAX, num[x]) - opof;
num[x] = opof[tnum[x]];
return num[x];
}
void Encode(int N, int A[], int B[]) {
ll i;
for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
for (i = 0; i < N - 1; i++) adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
dfs(0);
for (i = 0; i < N; i++) {
Code(i, ord[i] * (MAX) + tnum[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400
ll opof[MAX];
void InitDevice() {
ll i;
for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
}
int Answer(long long S, long long T) {
ll sl, sr, tl, tr;
sl = S / MAX;
tl = T / MAX;
sr = sl + opof[S % MAX];
tr = tl + opof[T % MAX];
if (sl <= tl && tr <= sr) return 1;
else if (tl <= sl && sr <= tr) return 0;
else return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7684 KB |
Output is correct |
2 |
Correct |
5 ms |
7696 KB |
Output is correct |
3 |
Correct |
4 ms |
7684 KB |
Output is correct |
4 |
Correct |
4 ms |
7692 KB |
Output is correct |
5 |
Correct |
4 ms |
7692 KB |
Output is correct |
6 |
Correct |
4 ms |
7680 KB |
Output is correct |
7 |
Correct |
4 ms |
7776 KB |
Output is correct |
8 |
Correct |
4 ms |
7692 KB |
Output is correct |
9 |
Correct |
5 ms |
7716 KB |
Output is correct |
10 |
Correct |
4 ms |
7680 KB |
Output is correct |
11 |
Correct |
4 ms |
7692 KB |
Output is correct |
12 |
Correct |
4 ms |
7684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
16292 KB |
Output is correct - L = 298801 |
2 |
Correct |
153 ms |
16160 KB |
Output is correct - L = 314001 |
3 |
Correct |
151 ms |
16276 KB |
Output is correct - L = 289201 |
4 |
Correct |
152 ms |
16344 KB |
Output is correct - L = 290401 |
5 |
Correct |
450 ms |
45764 KB |
Output is correct - L = 119782401 |
6 |
Correct |
430 ms |
45812 KB |
Output is correct - L = 121283201 |
7 |
Correct |
392 ms |
45616 KB |
Output is correct - L = 122337601 |
8 |
Correct |
406 ms |
47100 KB |
Output is correct - L = 133016401 |
9 |
Correct |
345 ms |
46140 KB |
Output is correct - L = 199133201 |
10 |
Correct |
332 ms |
46160 KB |
Output is correct - L = 197087601 |
11 |
Correct |
337 ms |
46304 KB |
Output is correct - L = 228080401 |
12 |
Correct |
324 ms |
46120 KB |
Output is correct - L = 206878401 |
13 |
Correct |
379 ms |
46140 KB |
Output is correct - L = 159570001 |
14 |
Correct |
396 ms |
45932 KB |
Output is correct - L = 130201201 |
15 |
Correct |
160 ms |
16564 KB |
Output is correct - L = 294801 |
16 |
Correct |
179 ms |
16556 KB |
Output is correct - L = 299201 |
17 |
Correct |
161 ms |
16524 KB |
Output is correct - L = 288001 |
18 |
Correct |
377 ms |
45236 KB |
Output is correct - L = 217220401 |
19 |
Correct |
389 ms |
45416 KB |
Output is correct - L = 100000001 |
20 |
Correct |
384 ms |
45236 KB |
Output is correct - L = 100000001 |
21 |
Correct |
381 ms |
45960 KB |
Output is correct - L = 206878001 |
22 |
Correct |
406 ms |
45076 KB |
Output is correct - L = 100723601 |
23 |
Correct |
380 ms |
44944 KB |
Output is correct - L = 100993601 |
24 |
Correct |
389 ms |
45076 KB |
Output is correct - L = 102545601 |
25 |
Correct |
382 ms |
44780 KB |
Output is correct - L = 102996801 |
26 |
Correct |
398 ms |
44532 KB |
Output is correct - L = 104271201 |
27 |
Correct |
402 ms |
44404 KB |
Output is correct - L = 104613601 |