Submission #427285

#	Time	Username	Problem	Language	Result	Execution time	Memory
427285		jjang36524	City (JOI17_city)	C++14	100 / 100	672 ms	53348 KiB

Encoder

#include "Encoder.h"
#include "Device.h"

#include <vector>
using namespace std;
static vector<int>h;
static vector<int>link[250100];
static void init()
{
    h.clear();
    int s=1;
    int tl=21;
    h.push_back(s);
    while(tl)
    {
        s=max((double)s+1,s*1.1);
        h.push_back(s);
        if(s>=250000)
            tl--;
    }
}
static int l[250100],r[250100],c,s[250100];
static void dfs(int n,int p)
{
    l[n]=c++;
    int i;
    for(i=0;i<link[n].size();i++)
    {
        if(link[n][i]!=p)
        {
            dfs(link[n][i],n);
        }
    }
    r[n]=c=(*lower_bound(h.begin(),h.end(),c-l[n]))+l[n];
    s[n]=lower_bound(h.begin(),h.end(),c-l[n])-h.begin();
}
void Encode(int N, int A[], int B[])
{
    init();
	for (int i = 1; i < N; ++i)
	{
		link[A[i-1]].push_back(B[i-1]);
		link[B[i-1]].push_back(A[i-1]);
	}
	dfs(0,-1);
	for(int i=0;i<N;i++)
	{
        Code(i,l[i]*h.size()+s[i]);
	}
}

Device

#include "Device.h"
#include <vector>
using namespace std;
static vector<int>h;
static void initt()
{
    int s=1;
    int tl=21;
    h.push_back(s);
    while(tl)
    {
        s=max((double)s+1,s*1.1);
        h.push_back(s);
        if(s>=250000)
            tl--;
    }
}
void InitDevice()
{
    initt();
}

int Answer(long long S, long long T)
{
    int sf=S/h.size();
    int tf=T/h.size();
    int se=h[S%h.size()]+sf;
    int te=h[T%h.size()]+tf;
    if(sf<=tf&&te<=se)
        return 1;
    if(tf<=sf&&se<=te)
    return 0;
    return 2;
}

Compilation message (stderr)

Encoder.cpp: In function 'void dfs(int, int)':
Encoder.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(i=0;i<link[n].size();i++)
      |             ~^~~~~~~~~~~~~~~

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