# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
126110 |
2019-07-07T05:08:47 Z |
tjd229 |
City (JOI17_city) |
C++14 |
|
572 ms |
70616 KB |
#include "Encoder.h"
#include <vector>
using namespace std;
vector<int> edge[250000];
vector<int> range;
int in[250000],p[250000];
int cnt;
void dfs(int x,int from) {
in[x] =cnt++;
for (auto to : edge[x]) {
if (to == from) continue;
dfs(to, x);
}
if (in[x] == cnt - 1) return;
int &e=p[x];
while (in[x] + range[e] < cnt - 1) ++e;
cnt = in[x] + range[e] + 1;
}
void Encode(int N, int A[], int B[])
{
const double r = 1.055645;
//const double r = 1.120438;
range.push_back(0);
for (int i = 1;i<256; ++i) {
int ar = r * range.back();
if (range.back() == ar) ++ar;
range.push_back(ar);
}
for (int i = 0; i < N-1; ++i) {
edge[B[i]].push_back(A[i]);
edge[A[i]].push_back(B[i]);
}
dfs(0,-1);
for (int i = 0; i < N ; ++i)
Code(i, in[i] + (p[i] << 20));
}
#include "Device.h"
#include <vector>
using namespace std;
vector<int> a;
void InitDevice()
{
const double r = 1.055645;
a.push_back(0);
for (int i = 1; i < 256; ++i) {
int ar = a.back()*r;
if (a.back() == ar)++ar;
a.push_back(ar);
}
}
int Answer(long long S, long long T)
{
int ss = S & ((1 << 20) - 1);
int ts= T & ((1 << 20) - 1);
int se = ss+a[S >> 20];
int te = ts+a[T >> 20];
if (ss <= ts && te <= se) return 1;
if (ts <= ss && se <= te) return 0;
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12272 KB |
Output is correct |
2 |
Correct |
9 ms |
12528 KB |
Output is correct |
3 |
Correct |
9 ms |
12272 KB |
Output is correct |
4 |
Correct |
9 ms |
12528 KB |
Output is correct |
5 |
Correct |
11 ms |
12272 KB |
Output is correct |
6 |
Correct |
10 ms |
12528 KB |
Output is correct |
7 |
Correct |
9 ms |
12528 KB |
Output is correct |
8 |
Correct |
9 ms |
12528 KB |
Output is correct |
9 |
Correct |
9 ms |
12528 KB |
Output is correct |
10 |
Correct |
9 ms |
12528 KB |
Output is correct |
11 |
Correct |
9 ms |
12528 KB |
Output is correct |
12 |
Correct |
9 ms |
12528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
26392 KB |
Output is correct - L = 101711872 |
2 |
Correct |
204 ms |
26536 KB |
Output is correct - L = 101711872 |
3 |
Correct |
200 ms |
26608 KB |
Output is correct - L = 100663296 |
4 |
Correct |
201 ms |
26616 KB |
Output is correct - L = 101711872 |
5 |
Correct |
540 ms |
69104 KB |
Output is correct - L = 218103808 |
6 |
Correct |
540 ms |
69088 KB |
Output is correct - L = 218103808 |
7 |
Correct |
534 ms |
68992 KB |
Output is correct - L = 219152384 |
8 |
Correct |
538 ms |
68336 KB |
Output is correct - L = 218103808 |
9 |
Correct |
458 ms |
70616 KB |
Output is correct - L = 229638144 |
10 |
Correct |
478 ms |
70608 KB |
Output is correct - L = 231735296 |
11 |
Correct |
455 ms |
69584 KB |
Output is correct - L = 231735296 |
12 |
Correct |
482 ms |
68792 KB |
Output is correct - L = 231735296 |
13 |
Correct |
491 ms |
69864 KB |
Output is correct - L = 223346688 |
14 |
Correct |
506 ms |
69360 KB |
Output is correct - L = 220200960 |
15 |
Correct |
209 ms |
26552 KB |
Output is correct - L = 101711872 |
16 |
Correct |
200 ms |
26608 KB |
Output is correct - L = 101711872 |
17 |
Correct |
201 ms |
26352 KB |
Output is correct - L = 100663296 |
18 |
Correct |
514 ms |
69344 KB |
Output is correct - L = 230686720 |
19 |
Correct |
495 ms |
69336 KB |
Output is correct - L = 230686720 |
20 |
Correct |
524 ms |
69664 KB |
Output is correct - L = 230686720 |
21 |
Correct |
514 ms |
69344 KB |
Output is correct - L = 230686720 |
22 |
Correct |
562 ms |
69336 KB |
Output is correct - L = 230686720 |
23 |
Correct |
530 ms |
69344 KB |
Output is correct - L = 230686720 |
24 |
Correct |
548 ms |
69312 KB |
Output is correct - L = 229638144 |
25 |
Correct |
558 ms |
69104 KB |
Output is correct - L = 228589568 |
26 |
Correct |
572 ms |
68872 KB |
Output is correct - L = 227540992 |
27 |
Correct |
556 ms |
69152 KB |
Output is correct - L = 226492416 |