# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
118379 |
2019-06-18T20:32:55 Z |
Mamnoon_Siam |
City (JOI17_city) |
C++17 |
|
545 ms |
66536 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const double R = 1.054;
const int maxn = 2.5e5 + 5;
int tym = 0;
vector<int> lg, g[maxn];
int length(int x) {
return *lower_bound(lg.begin(), lg.end(), x); }
int Log(int x) {
return lower_bound(lg.begin(), lg.end(), x) - lg.begin(); }
void dfs(int u, int p) {
int L = tym++;
for(int v : g[u]) if(v != p) {
dfs(v, u);
}
tym = L + length(tym - L);
Code(u, L << 8 | Log(tym - L));
}
void Encode(int N, int A[], int B[]) {
{
lg.clear();
double p = 1;
while(p < 1000000000.0) {
lg.emplace_back(floor(p));
p *= R;
}
sort(lg.begin(), lg.end());
lg.erase(unique(lg.begin(), lg.end()), lg.end());
}
for(int i = 0; i < N - 1; i++) {
int u = A[i], v = B[i];
g[u].emplace_back(v);
g[v].emplace_back(u);
} dfs(0, -1);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define lg antilog
const double R = 1.054;
const int maxn = 2.5e5 + 5;
vector<int> lg;
void InitDevice() {
double p = 1;
while(p < 1000000000.0) {
lg.emplace_back(floor(p));
p *= R;
}
sort(lg.begin(), lg.end());
lg.erase(unique(lg.begin(), lg.end()), lg.end());
}
pair<int, int> decode(long long code) {
return {code >> 8, (code >> 8) + lg[code & ((1 << 8) - 1)] - 1};
}
int Answer(long long u, long long v) {
int ul, ur, vl, vr;
tie(ul, ur) = decode(u);
tie(vl, vr) = decode(v);
if(vl <= ul and ur <= vr) return 0;
if(ul <= vl and vr <= ur) return 1;
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12544 KB |
Output is correct |
2 |
Correct |
8 ms |
12544 KB |
Output is correct |
3 |
Correct |
8 ms |
12544 KB |
Output is correct |
4 |
Correct |
9 ms |
12544 KB |
Output is correct |
5 |
Correct |
9 ms |
12544 KB |
Output is correct |
6 |
Correct |
8 ms |
12544 KB |
Output is correct |
7 |
Correct |
8 ms |
12544 KB |
Output is correct |
8 |
Correct |
8 ms |
12544 KB |
Output is correct |
9 |
Correct |
8 ms |
12544 KB |
Output is correct |
10 |
Correct |
9 ms |
12288 KB |
Output is correct |
11 |
Correct |
9 ms |
12512 KB |
Output is correct |
12 |
Correct |
9 ms |
12288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
170 ms |
26360 KB |
Output is correct - L = 187136 |
2 |
Correct |
169 ms |
26656 KB |
Output is correct - L = 199424 |
3 |
Correct |
168 ms |
26608 KB |
Output is correct - L = 192512 |
4 |
Correct |
169 ms |
26352 KB |
Output is correct - L = 196608 |
5 |
Correct |
500 ms |
64752 KB |
Output is correct - L = 80686848 |
6 |
Correct |
529 ms |
65032 KB |
Output is correct - L = 79586304 |
7 |
Correct |
538 ms |
64752 KB |
Output is correct - L = 77641728 |
8 |
Correct |
513 ms |
64496 KB |
Output is correct - L = 100383232 |
9 |
Correct |
465 ms |
66520 KB |
Output is correct - L = 139817728 |
10 |
Correct |
453 ms |
66520 KB |
Output is correct - L = 138472704 |
11 |
Correct |
460 ms |
66536 KB |
Output is correct - L = 153785344 |
12 |
Correct |
448 ms |
66520 KB |
Output is correct - L = 138432768 |
13 |
Correct |
487 ms |
66248 KB |
Output is correct - L = 104320256 |
14 |
Correct |
500 ms |
65136 KB |
Output is correct - L = 82966784 |
15 |
Correct |
172 ms |
26608 KB |
Output is correct - L = 192256 |
16 |
Correct |
172 ms |
26296 KB |
Output is correct - L = 198144 |
17 |
Correct |
201 ms |
26608 KB |
Output is correct - L = 184064 |
18 |
Correct |
487 ms |
65168 KB |
Output is correct - L = 145906944 |
19 |
Correct |
545 ms |
65304 KB |
Output is correct - L = 63999744 |
20 |
Correct |
535 ms |
65264 KB |
Output is correct - L = 63999744 |
21 |
Correct |
512 ms |
65248 KB |
Output is correct - L = 138432512 |
22 |
Correct |
507 ms |
65248 KB |
Output is correct - L = 65110272 |
23 |
Correct |
499 ms |
64736 KB |
Output is correct - L = 65283072 |
24 |
Correct |
520 ms |
65008 KB |
Output is correct - L = 65562880 |
25 |
Correct |
521 ms |
64976 KB |
Output is correct - L = 66335232 |
26 |
Correct |
544 ms |
65008 KB |
Output is correct - L = 67560192 |
27 |
Correct |
520 ms |
65016 KB |
Output is correct - L = 68271360 |