Submission #1059022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059022		jamjanek	City (JOI17_city)	C++14	30 / 100	290 ms	57600 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>graf[250010];
int preorder[250010], post[250010], preit, postit;
void dfs(int x, int o){
	preorder[x]=preit++;
	for(auto j: graf[x])
		if(j!=o)
			dfs(j, x);
	post[x]=preit;
}

long long sumyp[250010];

void Encode(int n, int A[], int B[])
{
	int i;
	for(i=0;i<n-1;i++){
		graf[A[i]].push_back(B[i]);
		graf[B[i]].push_back(A[i]);
	}
	for(i=1;i<=250000;i++){
		sumyp[i] = sumyp[i-1]+(250000-i+1);
	}
	dfs(0,-1);
	for (int i = 0; i < n; ++i) {
		Code(i, sumyp[preorder[i]]+post[i]-preorder[i]);
	}
}

Device

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

long long sumypD[250010];


void InitDevice()
{
	int n=250000;
	for(int i=1;i<=n;i++){
		sumypD[i] = sumypD[i-1]+(n-i+1);
	}
	sumypD[250001]=1000000000000000000;
}
pair<int,int> zamien(long long x){
	int a = int(lower_bound(sumypD, sumypD+250002, x)-sumypD);
	a--;
	return {a, x-sumypD[a]+a};
}
int Answer(long long S, long long T)
{
	int X1,X2;
	int Y1,Y2;
	X1 = zamien(S).first;
	X2 = zamien(S).second;
	Y1 = zamien(T).first;
	Y2 = zamien(T).second;
//	printf("%lld\n", sumypD[0]);
//	cerr<<X1<<" "<<X2<<" "<<Y1<<" "<<Y2<<" "<<S<<" "<<T<<"\n";
	if(X1<=Y1 && X2>=Y2)return 1;
	if(Y1<=X1 && Y2>=X2)return 0;
	return 2;
	
}

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