Submission #49471

#	Time	Username	Problem	Language	Result	Execution time	Memory
49471		SpaimaCarpatilor	City (JOI17_city)	C++17	100 / 100	542 ms	64280 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000, K = 252, maxM = 1000000;
int nr = 0, l[250009], length[250009], a[50009], firstAfter[maxM];
long long partialS[250009];
vector < int > v[250009];

void initA ()
{
    a[1] = 1;
    for (int i=2; i<=K; i++)
    {
        a[i] = (int) ((double) a[i - 1] * 1.05);
        if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
    }
    int j = 1;
    for (int i=1; i<=a[K]; i++)
    {
        while (a[j] < i)
            j ++;
        firstAfter[i] = j;
    }
}

void dfs (int nod, int tata)
{
    l[nod] = ++nr;
    for (auto it : v[nod])
        if (it != tata)
            dfs (it, nod);
    int L = firstAfter[nr - l[nod] + 1];
    nr = l[nod] + a[L] - 1;
    length[nod] = L;
}

void Encode (int N, int A[], int B[])
{
    for (int i=0; i<N - 1; i++)
        v[A[i]].push_back (B[i]),
        v[B[i]].push_back (A[i]);
    initA ();
    dfs (0, -1);
	for (int i=0; i<N; i++)
		Code(i, 1LL * length[i] * maxM + l[i]);
}

Device

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000, K = 252, maxM = 1000000;
static int a[50009];

void InitDevice()
{
    a[1] = 1;
    for (int i=2; i<=K; i++)
    {
        a[i] = (int) ((double) a[i - 1] * 1.05);
        if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
    }
}

void decode (long long X, int &i, int &j)
{
    j = X / maxM, i = X % maxM;
    j = a[j] + i - 1;
}

int Answer (long long S, long long T)
{
    int lS, rS; decode (S, lS, rS);
    int lT, rT; decode (T, lT, rT);
    if (lT <= lS && rS <= rT) return 0;
    if (lS <= lT && rT <= rS) return 1;
	return 2;
}

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