Submission #1059149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059149		jamjanek	City (JOI17_city)	C++14	100 / 100	203 ms	55660 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>graf[250010];
long long preorder[250010], preit;
long long r[250010];

vector<long long>rozmiary;

void dfs(int x, int o){
	preorder[x]=preit++;
	for(auto j: graf[x])
		if(j!=o){
			dfs(j, x);
			r[x]+=r[j]+1;
		}
	long long pom = *lower_bound(rozmiary.begin(), rozmiary.end(), r[x]) - r[x];
	preit+=pom;
	r[x]+=pom;
}



void Encode(int n, int A[], int B[])
{
	rozmiary.push_back(0);
	int ile = 0;
	while(true){
		rozmiary.push_back(max(rozmiary.back()+1, (long long)(1.1d*rozmiary.back())));
		if(rozmiary.back()>=250000)ile++;
		if(ile==19)break;
	}

	int i;
	for(i=0;i<n-1;i++){
		graf[A[i]].push_back(B[i]);
		graf[B[i]].push_back(A[i]);
	}
	dfs(0,-1);
//	for(int i=0;i<n;i++)
//		printf("%d: %d %d %d\n", i, preorder[i], r[i], int(lower_bound(rozmiary.begin(), rozmiary.end(), r[i])-rozmiary.begin()));
	for (int i = 0; i < n; ++i) {
		Code(i, (long long)preorder[i]*rozmiary.size()+(long long)(lower_bound(rozmiary.begin(), rozmiary.end(), r[i])-rozmiary.begin()));
	}
}

Device

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


vector<long long>rozmiary1;
void InitDevice()
{
	rozmiary1.push_back(0);
	int ile = 0;
	while(true){
		rozmiary1.push_back(max(rozmiary1.back()+1, (long long)(1.1d*rozmiary1.back())));
		if(rozmiary1.back()>=250000)ile++;
		if(ile==19)break;
	}
}
int Answer(long long S, long long T)
{
	long long X1 = S/rozmiary1.size(),X2 = rozmiary1[S%rozmiary1.size()];
	long long Y1 = T/rozmiary1.size(),Y2 = rozmiary1[T%rozmiary1.size()];

//	cerr<<X1<<" "<<X2<<" "<<Y1<<" "<<Y2<<" "<<S<<" "<<T<<"\n";
	if(X1<=Y1 && X1+X2>=Y1)return 1;
	if(Y1<=X1 && Y2+Y1>=X1)return 0;
	return 2;
	
}

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