#include "Encoder.h"
#include <vector>
#include <algorithm>
static const int N = 250000 + 10;
typedef long long i64;
static std::vector<int> adj[N], r;
static void init() {
int i = 1;
for (; i < N; i += std::max<int>(1, .05 * i)) r.push_back(i);
for (int j = 20; j--; i += std::max<int>(1, .05 * i)) r.push_back(i);
}
static int left[N], right[N], tot;
static void dfs(int a, int fa = -1) {
left[a] = tot++;
for (int i = 0; i < adj[a].size(); ++i) if (adj[a][i] != fa) dfs(adj[a][i], a);
right[a] = tot = left[a] + *std::lower_bound(r.begin(), r.end(), tot - left[a]);
}
void Encode(int n, int a[], int b[]) {
init();
for (int i = 0; i < n - 1; ++i) adj[a[i]].push_back(b[i]), adj[b[i]].push_back(a[i]);
dfs(0);
for (int i = 0; i < n; ++i) {
int x = left[i], y = std::lower_bound(r.begin(), r.end(), right[i] - left[i]) - r.begin();
Code(i, y << 20 | x);
}
}
#include "Device.h"
#include <vector>
#include <algorithm>
static const int N = 250000 + 10;
typedef long long i64;
static std::vector<int> r;
void InitDevice() {
int i = 1;
for (; i < N; i += std::max<int>(1, .05 * i)) r.push_back(i);
for (int j = 20; j--; i += std::max<int>(1, .05 * i)) r.push_back(i);
}
static std::pair<int, int> solve(i64 x) {
int l = x & 0xfffff, y = x >> 20;
return std::make_pair(l, l + r[y]);
}
int Answer(i64 s, i64 t) {
std::pair<int, int> x = solve(s), y = solve(t);
if (y.first <= x.first && x.second <= y.second) return 0;
if (x.first <= y.first && y.second <= x.second) return 1;
return 2;
}
Compilation message
Encoder.cpp: In function 'void dfs(int, int)':
Encoder.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[a].size(); ++i) if (adj[a][i] != fa) dfs(adj[a][i], a);
~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12544 KB |
Output is correct |
2 |
Correct |
7 ms |
12544 KB |
Output is correct |
3 |
Correct |
7 ms |
12288 KB |
Output is correct |
4 |
Correct |
9 ms |
12544 KB |
Output is correct |
5 |
Correct |
9 ms |
12520 KB |
Output is correct |
6 |
Correct |
9 ms |
12544 KB |
Output is correct |
7 |
Correct |
9 ms |
12488 KB |
Output is correct |
8 |
Correct |
9 ms |
12288 KB |
Output is correct |
9 |
Correct |
7 ms |
12288 KB |
Output is correct |
10 |
Correct |
8 ms |
12288 KB |
Output is correct |
11 |
Correct |
9 ms |
12272 KB |
Output is correct |
12 |
Correct |
8 ms |
12288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
168 ms |
19296 KB |
Output is correct - L = 109051904 |
2 |
Correct |
170 ms |
19560 KB |
Output is correct - L = 110100480 |
3 |
Correct |
168 ms |
19528 KB |
Output is correct - L = 108003328 |
4 |
Correct |
170 ms |
19368 KB |
Output is correct - L = 109051904 |
5 |
Correct |
522 ms |
55296 KB |
Output is correct - L = 238026752 |
6 |
Correct |
531 ms |
55288 KB |
Output is correct - L = 239075328 |
7 |
Correct |
515 ms |
55320 KB |
Output is correct - L = 239075328 |
8 |
Correct |
517 ms |
54712 KB |
Output is correct - L = 241172480 |
9 |
Correct |
437 ms |
56400 KB |
Output is correct - L = 249561088 |
10 |
Correct |
510 ms |
57928 KB |
Output is correct - L = 251658240 |
11 |
Correct |
412 ms |
56528 KB |
Output is correct - L = 252706816 |
12 |
Correct |
434 ms |
57760 KB |
Output is correct - L = 252706816 |
13 |
Correct |
494 ms |
57072 KB |
Output is correct - L = 244318208 |
14 |
Correct |
510 ms |
56776 KB |
Output is correct - L = 241172480 |
15 |
Correct |
167 ms |
20736 KB |
Output is correct - L = 109051904 |
16 |
Correct |
168 ms |
20720 KB |
Output is correct - L = 109051904 |
17 |
Correct |
168 ms |
20536 KB |
Output is correct - L = 109051904 |
18 |
Correct |
477 ms |
56808 KB |
Output is correct - L = 251658240 |
19 |
Correct |
480 ms |
56784 KB |
Output is correct - L = 251658240 |
20 |
Correct |
475 ms |
56800 KB |
Output is correct - L = 251658240 |
21 |
Correct |
502 ms |
56792 KB |
Output is correct - L = 250609664 |
22 |
Correct |
509 ms |
56664 KB |
Output is correct - L = 250609664 |
23 |
Correct |
501 ms |
56824 KB |
Output is correct - L = 250609664 |
24 |
Correct |
506 ms |
56304 KB |
Output is correct - L = 249561088 |
25 |
Correct |
537 ms |
56328 KB |
Output is correct - L = 248512512 |
26 |
Correct |
549 ms |
56096 KB |
Output is correct - L = 247463936 |
27 |
Correct |
548 ms |
56400 KB |
Output is correct - L = 246415360 |