# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1005455 |
2024-06-22T13:05:47 Z |
79brue |
City (JOI17_city) |
C++17 |
|
226 ms |
57252 KB |
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
const int M = 300;
int n;
ll len[512] = {0};
void init(){
for(int i=1; i<=M; i++){
len[i] = round(double(len[i-1]) * 1.05);
if(len[i] == len[i-1]) len[i]++;
}
}
vector<int> link[250005];
ll in[250005], out[250002], inCnt=0, t[250002];
void dfs(int x, int p=-1){
in[x] = ++inCnt;
for(int y: link[x]){
if(y==p) continue;
dfs(y, x);
}
t[x] = lower_bound(len, len+M+1, inCnt - in[x]) - len;
inCnt = out[x] = in[x] + len[t[x]];
}
void encode(int N, int A[], int B[]){
init();
n = N;
for(int i=0; i<n-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
dfs(0);
for(int i=0; i<n; i++){
assert(in[i] < (1<<19) && out[i] - in[i] < len[255]);
Code(i, in[i] << 8 | t[i]);
}
}
}
void Encode(int N, int A[], int B[]){
encode(N, A, B);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
const int M = 300;
ll len[512] = {0};
void init(){
for(int i=1; i<=M; i++){
len[i] = round(double(len[i-1]) * 1.05);
if(len[i] == len[i-1]) len[i]++;
}
}
}
void InitDevice(){
init();
}
int Answer(ll S, ll T){
ll SL = S >> 8, SR = SL + len[S & 255];
ll TL = T >> 8, TR = TL + len[T & 255];
if(SL<=TL&&TR<=SR) return 1;
if(TL<=SL&&SR<=TR) return 0;
return 2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
15136 KB |
Output is correct |
2 |
Correct |
2 ms |
15136 KB |
Output is correct |
3 |
Correct |
2 ms |
15136 KB |
Output is correct |
4 |
Correct |
2 ms |
15136 KB |
Output is correct |
5 |
Correct |
2 ms |
15136 KB |
Output is correct |
6 |
Correct |
2 ms |
15136 KB |
Output is correct |
7 |
Correct |
2 ms |
15124 KB |
Output is correct |
8 |
Correct |
2 ms |
15116 KB |
Output is correct |
9 |
Correct |
2 ms |
15124 KB |
Output is correct |
10 |
Correct |
2 ms |
15136 KB |
Output is correct |
11 |
Correct |
1 ms |
15124 KB |
Output is correct |
12 |
Correct |
1 ms |
15136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
22828 KB |
Output is correct - L = 190208 |
2 |
Correct |
94 ms |
29460 KB |
Output is correct - L = 198656 |
3 |
Correct |
94 ms |
29744 KB |
Output is correct - L = 187392 |
4 |
Correct |
93 ms |
29748 KB |
Output is correct - L = 190208 |
5 |
Correct |
207 ms |
56516 KB |
Output is correct - L = 77004032 |
6 |
Correct |
226 ms |
56532 KB |
Output is correct - L = 79570688 |
7 |
Correct |
198 ms |
56516 KB |
Output is correct - L = 78318848 |
8 |
Correct |
209 ms |
56412 KB |
Output is correct - L = 89360384 |
9 |
Correct |
189 ms |
57252 KB |
Output is correct - L = 127458048 |
10 |
Correct |
192 ms |
57240 KB |
Output is correct - L = 126135040 |
11 |
Runtime error |
68 ms |
53448 KB |
Execution killed with signal 6 |
12 |
Halted |
0 ms |
0 KB |
- |