# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
551987 |
2022-04-22T04:50:53 Z |
LucaDantas |
City (JOI17_city) |
C++17 |
|
426 ms |
39944 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 = 1+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)];
}
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 |
4 ms |
6800 KB |
Output is correct |
2 |
Correct |
4 ms |
6796 KB |
Output is correct |
3 |
Correct |
4 ms |
6804 KB |
Output is correct |
4 |
Correct |
3 ms |
6796 KB |
Output is correct |
5 |
Correct |
4 ms |
6812 KB |
Output is correct |
6 |
Correct |
3 ms |
6812 KB |
Output is correct |
7 |
Correct |
4 ms |
6804 KB |
Output is correct |
8 |
Correct |
4 ms |
6800 KB |
Output is correct |
9 |
Correct |
4 ms |
6788 KB |
Output is correct |
10 |
Correct |
4 ms |
6800 KB |
Output is correct |
11 |
Correct |
4 ms |
6804 KB |
Output is correct |
12 |
Correct |
4 ms |
6796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
15360 KB |
Output is correct - L = 380160 |
2 |
Correct |
179 ms |
16556 KB |
Output is correct - L = 393216 |
3 |
Correct |
166 ms |
16620 KB |
Output is correct - L = 384512 |
4 |
Correct |
169 ms |
16576 KB |
Output is correct - L = 397056 |
5 |
Correct |
419 ms |
39944 KB |
Output is correct - L = 154639872 |
6 |
Correct |
399 ms |
38616 KB |
Output is correct - L = 153696000 |
7 |
Correct |
400 ms |
38632 KB |
Output is correct - L = 158495488 |
8 |
Correct |
426 ms |
38452 KB |
Output is correct - L = 185795072 |
9 |
Correct |
372 ms |
39376 KB |
Output is correct - L = 264927232 |
10 |
Correct |
343 ms |
39292 KB |
Output is correct - L = 262222848 |
11 |
Partially correct |
335 ms |
39340 KB |
Output is partially correct - L = 289010176 |
12 |
Correct |
374 ms |
39384 KB |
Output is correct - L = 262143488 |
13 |
Correct |
378 ms |
39004 KB |
Output is correct - L = 212290304 |
14 |
Correct |
374 ms |
38864 KB |
Output is correct - L = 165676288 |
15 |
Correct |
167 ms |
16568 KB |
Output is correct - L = 384512 |
16 |
Correct |
167 ms |
16632 KB |
Output is correct - L = 392960 |
17 |
Correct |
159 ms |
16580 KB |
Output is correct - L = 368896 |
18 |
Partially correct |
426 ms |
38864 KB |
Output is partially correct - L = 275248896 |
19 |
Correct |
390 ms |
38780 KB |
Output is correct - L = 127994880 |
20 |
Correct |
366 ms |
38988 KB |
Output is correct - L = 127994880 |
21 |
Correct |
373 ms |
38876 KB |
Output is correct - L = 262142976 |
22 |
Correct |
367 ms |
38820 KB |
Output is correct - L = 128387584 |
23 |
Correct |
358 ms |
38904 KB |
Output is correct - L = 128733184 |
24 |
Correct |
377 ms |
38700 KB |
Output is correct - L = 130504192 |
25 |
Correct |
378 ms |
38664 KB |
Output is correct - L = 130963712 |
26 |
Correct |
389 ms |
38680 KB |
Output is correct - L = 132506112 |
27 |
Correct |
382 ms |
38608 KB |
Output is correct - L = 132846336 |