Submission #1005444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005444		79brue	City (JOI17_city)	C++17	8 / 100	90 ms	20640 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace{
    const int M = 850;
    int n;
    ll len[1024] = {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, 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;
        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++) Code(i, in[i] << 10 | t[i]);
    }
}

void Encode(int N, int A[], int B[]){
    encode(N, A, B);
}

Device

#include "Device.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace{
    const int M = 850;
    ll len[1024] = {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 >> 10, SR = SL + len[S & 1023];
    ll TL = T >> 10, TR = TL + len[T & 1023];
    if(SL<=TL&&TR<=SR) return 1;
    if(TL<=SL&&SR<=TR) return 0;
    return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92