Submission #1157805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157805		jerzyk	City (JOI17_city)	C++20	100 / 100	221 ms	32064 KiB

Encoder

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;

namespace A
{

const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<18;
const int K1 = 24, K2 = 7;
const ld P = 1.12;
ll pot[(1<<K2) + 10];
vector<int>ed[N];
int tab[N];
bool vis[N];
ll pre[N], pos[N];
int num[N];

void Do()
{
    pot[0] = 0;
    pot[1] = 1;
    ld cur = 1.0;
    for(int i = 2; i < (1<<K2); ++i)
    {
        while((ll)cur <= pot[i - 1])
            cur *= P;
        pot[i] = cur;
        //if(i <= 20)
            //cout << i << " " << pot[i] << "\n";
    }
}

int Get(ll x)
{
    return (lower_bound(pot, pot + 1 + (1<<K2), x) - pot);
}

void DFS(int v)
{
    vis[v] = 1;
    pos[v] = pre[v];
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(vis[ed[v][i]]) continue;
        pre[ed[v][i]] = pos[v] + 1;
        DFS(ed[v][i]);
        pos[v] = pos[ed[v][i]];
    }
    ll d = pos[v] - pre[v];
    num[v] = Get(d);
    pos[v] = pre[v] + pot[num[v]];
    //cout << "DFS: " << v << " " << pre[v] << " " << pos[v] << " " << num[v] << "\n";
}

ll C(int v)
{
    return (ll)(1<<K2) * pre[v] + (ll)num[v];
}

}

void Encode(int _N, int A[], int B[])
{
    using namespace A;

    Do();
    int n = _N;
    for(int i = 0; i < n - 1; ++i)
    {
        ed[A[i]].pb(B[i]);
        ed[B[i]].pb(A[i]);
    }
    DFS(0);


    for(int i = 0; i < n; ++i)
        Code(i, C(i));
}

Device

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;

namespace B
{

const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<18;
const int K1 = 24, K2 = 7;
const ld P = 1.12;
ll pot[(1<<K2) + 10];

void Do()
{
    pot[0] = 0;
    pot[1] = 1;
    ld cur = 1.0;
    for(int i = 2; i < (1<<K2); ++i)
    {
        while((ll)cur <= pot[i - 1])
            cur *= P;
        pot[i] = cur;
    }
}


pair<ll, ll> T(ll x)
{
    return make_pair(x / (ll)(1<<K2), x % (ll)(1<<K2));
}

}

void InitDevice()
{
    using namespace B;
    Do();
}

int Answer(ll _S, ll _T)
{
    using namespace B;
    pair<ll, ll> a = T(_S), b = T(_T);
    a.nd = a.st + pot[a.nd];
    b.nd = b.st + pot[b.nd];
    if(a.st <= b.st && a.nd >= b.nd)
        return 1;
    if(b.st <= a.st && b.nd >= a.nd)
        return 0;
    return 2;
}

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