oj.uz

Submission #1005457

# Submission time Handle Problem Language Result Execution time Memory
1005457 2024-06-22T13:07:53 Z 79brue City (JOI17_city) C++17
100 / 100
 225 ms 55652 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));
//            assert(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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13092 KB Output is correct
2 Correct 2 ms 13084 KB Output is correct
3 Correct 2 ms 13072 KB Output is correct
4 Correct 2 ms 13076 KB Output is correct
5 Correct 1 ms 13076 KB Output is correct
6 Correct 1 ms 13076 KB Output is correct
7 Correct 2 ms 13076 KB Output is correct
8 Correct 2 ms 13088 KB Output is correct
9 Correct 1 ms 13088 KB Output is correct
10 Correct 2 ms 13076 KB Output is correct
11 Correct 2 ms 13088 KB Output is correct
12 Correct 2 ms 13088 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 20520 KB Output is correct - L = 190208
2 Correct 92 ms 20624 KB Output is correct - L = 198656
3 Correct 89 ms 20592 KB Output is correct - L = 187392
4 Correct 89 ms 20544 KB Output is correct - L = 190208
5 Correct 213 ms 41144 KB Output is correct - L = 77004032
6 Correct 194 ms 41352 KB Output is correct - L = 79570688
7 Correct 211 ms 41132 KB Output is correct - L = 78318848
8 Correct 201 ms 40792 KB Output is correct - L = 89360384
9 Correct 173 ms 41720 KB Output is correct - L = 127458048
10 Correct 203 ms 41740 KB Output is correct - L = 126135040
11 Correct 188 ms 48628 KB Output is correct - L = 145969152
12 Correct 196 ms 55652 KB Output is correct - L = 132399872
13 Correct 191 ms 55348 KB Output is correct - L = 102113280
14 Correct 221 ms 54708 KB Output is correct - L = 83490048
15 Correct 94 ms 27652 KB Output is correct - L = 186112
16 Correct 102 ms 27664 KB Output is correct - L = 197888
17 Correct 93 ms 27488 KB Output is correct - L = 184832
18 Correct 199 ms 54516 KB Output is correct - L = 139018752
19 Correct 208 ms 54624 KB Output is correct - L = 64000000
20 Correct 200 ms 54452 KB Output is correct - L = 64000000
21 Correct 208 ms 54716 KB Output is correct - L = 132399616
22 Correct 203 ms 54708 KB Output is correct - L = 64460800
23 Correct 207 ms 54644 KB Output is correct - L = 64633600
24 Correct 206 ms 54752 KB Output is correct - L = 65626880
25 Correct 210 ms 54352 KB Output is correct - L = 65915648
26 Correct 225 ms 54740 KB Output is correct - L = 66731264
27 Correct 210 ms 54444 KB Output is correct - L = 66950400