Submission #218132

#	Time	Username	Problem	Language	Result	Execution time	Memory
218132		patrikpavic2	City (JOI17_city)	C++17	30 / 100	556 ms	82904 KiB

Encoder

#include "Encoder.h"
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;

const int N = 5e5 + 500;

int L[N], R[N], cur = 0, n;
vector < int > v[N];

void dfs(int x,int lst){
	L[x] = cur++;
	for(int y : v[x])
		if(y != lst)
			dfs(y, x);
	R[x] = cur;
}


void Encode(int nn, int u1[], int u2[]){
	n = nn;
	for(int i = 0;i + 1 < n;i++)
		v[u1[i]].PB(u2[i]),
		v[u2[i]].PB(u1[i]);
	dfs(0, 0);
	for(int i = 0;i < n;i++){
		//printf("i = %d kod = %lld\n", i, (ll)R[i] * (R[i] - 1) / 2LL + L[i]);
		Code(i, (ll)R[i] * (ll)(R[i] - 1) / 2LL + (ll)L[i]);
	}
}

Device

#include "Device.h"
#include <cstdio>

typedef long long ll;

void InitDevice(){
	return;
}

inline int get_R(ll X){
	int ret = 0;
	for(int i = 18;i >= 0;i--){
		ret += (1 << i);
		if((ll)ret * (ll)(ret - 1) / 2LL > X)
			ret -= (1 << i);
	}
	return ret;
}


int Answer(ll A, ll B){
	//printf("A = %lld B = %lld\n", A, B);
	int R_A = get_R(A);
	int R_B = get_R(B);
	int L_A = A - (ll)R_A * (R_A - 1) / 2LL;
	int L_B = B - (ll)R_B * (R_B - 1) / 2LL;
	//printf("L_A = %d R_A = %d\n", L_A, R_A);
	//printf("L_B = %d R_B = %d\n", L_B, R_B);
	if(L_B <= L_A && L_A < R_B)
		return 0;
	if(L_A <= L_B && L_B < R_A)
		return 1;
	return 2;
}

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