# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
551988 |
2022-04-22T04:54:14 Z |
LucaDantas |
City (JOI17_city) |
C++17 |
|
465 ms |
38132 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1<<18;
constexpr double base = 1.05; // uso os intervalos em tamanho de potencias dessa base
vector<int> g[maxn];
static vector<int> val;
void set_val() {
val.push_back(1);
for(int i = 1; i < (1 << 8); i++) {
int aq = val.back() * base;
if(aq == val.back()) ++aq;
val.push_back(aq);
}
}
int find_pot(int x) { return lower_bound(val.begin(), val.end(), x) - val.begin(); }
int dfs(int u, int p, int in) {
int out = in+1;
for(int v : g[u]) if(v != p)
out = dfs(v, u, out);
int sz = out - in, d = find_pot(sz);
Code(u, (in<<8)|d);
return in + val[d];
}
void Encode(int N, int A[], int B[])
{
set_val();
for(int i = 0; i < N-1; i++)
g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
dfs(0, -1, 0);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
constexpr double base = 1.05;
static vector<int> val;
void InitDevice() {
val.push_back(1);
for(int i = 1; i < (1 << 8); i++) {
int aq = val.back() * base;
if(aq == val.back()) ++aq;
val.push_back(aq);
}
}
int Answer(long long S, long long T)
{
int in[2], out[2];
for(int rep = 0; rep < 2; rep++, swap(S, T)) {
in[rep] = S >> 8;
out[rep] = in[rep] + val[S % (1<<8)] - 1;
}
int vira = 0;
if(in[0] > in[1])
swap(in[0], in[1]), swap(out[0], out[1]), vira = 1;
return (out[0] >= in[1] ? 1^vira : 2);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6672 KB |
Output is correct |
2 |
Correct |
3 ms |
6672 KB |
Output is correct |
3 |
Correct |
3 ms |
6680 KB |
Output is correct |
4 |
Correct |
3 ms |
6672 KB |
Output is correct |
5 |
Correct |
4 ms |
6800 KB |
Output is correct |
6 |
Correct |
4 ms |
6800 KB |
Output is correct |
7 |
Correct |
5 ms |
6808 KB |
Output is correct |
8 |
Correct |
3 ms |
6796 KB |
Output is correct |
9 |
Correct |
4 ms |
6800 KB |
Output is correct |
10 |
Correct |
3 ms |
6800 KB |
Output is correct |
11 |
Correct |
3 ms |
6792 KB |
Output is correct |
12 |
Correct |
3 ms |
6800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
15288 KB |
Output is correct - L = 190976 |
2 |
Correct |
158 ms |
15240 KB |
Output is correct - L = 200704 |
3 |
Correct |
177 ms |
15232 KB |
Output is correct - L = 184832 |
4 |
Correct |
154 ms |
15188 KB |
Output is correct - L = 185600 |
5 |
Correct |
399 ms |
37396 KB |
Output is correct - L = 76660480 |
6 |
Correct |
442 ms |
37304 KB |
Output is correct - L = 77620992 |
7 |
Correct |
371 ms |
37416 KB |
Output is correct - L = 78295808 |
8 |
Correct |
465 ms |
37244 KB |
Output is correct - L = 85130240 |
9 |
Correct |
353 ms |
38132 KB |
Output is correct - L = 127444992 |
10 |
Correct |
344 ms |
38084 KB |
Output is correct - L = 126135808 |
11 |
Correct |
370 ms |
38128 KB |
Output is correct - L = 145971200 |
12 |
Correct |
328 ms |
38060 KB |
Output is correct - L = 132401920 |
13 |
Correct |
380 ms |
37808 KB |
Output is correct - L = 102124544 |
14 |
Correct |
413 ms |
37724 KB |
Output is correct - L = 83328512 |
15 |
Correct |
162 ms |
15332 KB |
Output is correct - L = 188416 |
16 |
Correct |
159 ms |
15380 KB |
Output is correct - L = 191232 |
17 |
Correct |
164 ms |
15188 KB |
Output is correct - L = 184064 |
18 |
Correct |
430 ms |
37696 KB |
Output is correct - L = 139020800 |
19 |
Correct |
356 ms |
37720 KB |
Output is correct - L = 63999744 |
20 |
Correct |
374 ms |
37708 KB |
Output is correct - L = 63999744 |
21 |
Correct |
385 ms |
37596 KB |
Output is correct - L = 132401664 |
22 |
Correct |
368 ms |
37468 KB |
Output is correct - L = 64462848 |
23 |
Correct |
419 ms |
37584 KB |
Output is correct - L = 64635648 |
24 |
Correct |
434 ms |
37456 KB |
Output is correct - L = 65628928 |
25 |
Correct |
408 ms |
37376 KB |
Output is correct - L = 65917696 |
26 |
Correct |
409 ms |
37372 KB |
Output is correct - L = 66733312 |
27 |
Correct |
442 ms |
37412 KB |
Output is correct - L = 66952448 |