Submission #363674

#	Time	Username	Problem	Language	Result	Execution time	Memory
363674		denkendoemeer	City (JOI17_city)	C++14	100 / 100	494 ms	54164 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>g[250005],r;
int in[250005],t[250005],u;
void dfs(int nod,int ta)
{
    in[nod]=u++;
    for(auto it:g[nod]){
        if (it!=ta)
            dfs(it,nod);
    }
    if (in[nod]==u-1)
        return ;
    int &ans=t[nod];
    while(in[nod]+r[ans]<u-1)
        ans++;
    u=in[nod]+r[ans]+1;
}
void Encode(int n,int a[],int b[])
{
    double d=1.050045;
    r.push_back(0);
    int i;
    for(i=1;i<256;i++){
        int aux=d*r.back();
        if (r.back()==aux)
            ++aux;
        r.push_back(aux);
    }
    for(i=0;i<n-1;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        Code(i,in[i]+(t[i]<<20));
}

Device

#include "Device.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>aux;
void InitDevice()
{
    double d=1.050045;
    aux.push_back(0);
    int i;
    for(i=1;i<256;i++){
        int nr=aux.back()*d;
        if (aux.back()==nr)
            ++nr;
        aux.push_back(nr);
    }
}
int Answer(ll s,ll t)
{
    int aux1,aux2,aux3,aux4;
    aux1=s&((1<<20)-1);
    aux2=t&((1<<20)-1);
    aux3=aux1+aux[s>>20];
    aux4=aux2+aux[t>>20];
    if (aux2<=aux1 && aux3<=aux4)
        return 0;
    if (aux1<=aux2 && aux4<=aux3)
        return 1;
    return 2;
}

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