Submission #700127

#	Time	Username	Problem	Language	Result	Execution time	Memory
700127		amunduzbaev	City (JOI17_city)	C++17	100 / 100	458 ms	47824 KiB

Encoder

#include "Encoder.h"
#include "bits/stdc++.h"
using namespace std;

void Encode(int n, int a[], int b[]){
	const int SZ = 223;

	int tot[SZ] = 
	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22,
	24, 26, 28, 30, 32, 34, 36, 38, 40, 43, 46, 49, 52, 55, 58, 61, 65, 69, 73, 77,
	81, 86, 91, 96, 101, 107, 113, 119, 125, 132, 139, 146, 154, 162, 171, 180, 190, 200, 211, 222,
	234, 246, 259, 272, 286, 301, 317, 333, 350, 368, 387, 407, 428, 450, 473, 497, 522, 549, 577, 606,
	637, 669, 703, 739, 776, 815, 856, 899, 944, 992, 1042, 1095, 1150, 1208, 1269, 1333, 1400, 1471, 1545, 1623,
	1705, 1791, 1881, 1976, 2075, 2179, 2288, 2403, 2524, 2651, 2784, 2924, 3071, 3225, 3387, 3557, 3735, 3922, 4119, 4325,
	4542, 4770, 5009, 5260, 5524, 5801, 6092, 6397, 6717, 7053, 7406, 7777, 8166, 8575, 9004, 9455, 9928, 10425, 10947, 11495,
	12070, 12674, 13308, 13974, 14673, 15407, 16178, 16987, 17837, 18729, 19666, 20650, 21683, 22768, 23907, 25103, 26359, 27677, 29061, 30515,
	32041, 33644, 35327, 37094, 38949, 40897, 42942, 45090, 47345, 49713, 52199, 54809, 57550, 60428, 63450, 66623, 69955, 73453, 77126, 80983,
	85033, 89285, 93750, 98438, 103360, 108529, 113956, 119654, 125637, 131919, 138515, 145441, 152714, 160350, 168368, 176787, 185627, 194909, 204655, 214888,
	225633, 236915, 248761, 261200, 274261, 287975, 302374, 317493, 333368, 350037, 367539, 385916, 405212, 425473, 446747, 469085, 492540, 517168, 543027, 570179,
	598688, 628623};
	
	vector<vector<int>> edges(n);
	for(int i=0;i<n-1;i++){
		edges[a[i]].push_back(b[i]);
		edges[b[i]].push_back(a[i]);
		//~ cout<<a[i]<<" "<<b[i]<<"\n";
	}
	int tin[n] {}, tout[n] {}, t = -1, sub[n] {};
	function<void(int, int)> dfs = [&](int u, int p){
		tin[u] = ++t;
		sub[u] = 1;
		for(auto x : edges[u]){
			if(x == p) continue;
			dfs(x, u);
			sub[u] += tot[tout[x]];
		}
		
		int j = lower_bound(tot, tot + SZ, sub[u]) - tot;
		assert(j < SZ);
		//~ sub[u] = tot[j];
		t = tin[u] + tot[j] - 1;
		tout[u] = j;
	};
	
	dfs(0, 0);
	for(int i=0;i<n;i++){
		//~ cout<<tin[i]<<" "<<tot[tout[i]]<<"\n";
		Code(i, tin[i] * 1ll * SZ + tout[i]);
	}
}

Device

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

const int SZ = 223;
int tot[SZ] = 
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22,
24, 26, 28, 30, 32, 34, 36, 38, 40, 43, 46, 49, 52, 55, 58, 61, 65, 69, 73, 77,
81, 86, 91, 96, 101, 107, 113, 119, 125, 132, 139, 146, 154, 162, 171, 180, 190, 200, 211, 222,
234, 246, 259, 272, 286, 301, 317, 333, 350, 368, 387, 407, 428, 450, 473, 497, 522, 549, 577, 606,
637, 669, 703, 739, 776, 815, 856, 899, 944, 992, 1042, 1095, 1150, 1208, 1269, 1333, 1400, 1471, 1545, 1623,
1705, 1791, 1881, 1976, 2075, 2179, 2288, 2403, 2524, 2651, 2784, 2924, 3071, 3225, 3387, 3557, 3735, 3922, 4119, 4325,
4542, 4770, 5009, 5260, 5524, 5801, 6092, 6397, 6717, 7053, 7406, 7777, 8166, 8575, 9004, 9455, 9928, 10425, 10947, 11495,
12070, 12674, 13308, 13974, 14673, 15407, 16178, 16987, 17837, 18729, 19666, 20650, 21683, 22768, 23907, 25103, 26359, 27677, 29061, 30515,
32041, 33644, 35327, 37094, 38949, 40897, 42942, 45090, 47345, 49713, 52199, 54809, 57550, 60428, 63450, 66623, 69955, 73453, 77126, 80983,
85033, 89285, 93750, 98438, 103360, 108529, 113956, 119654, 125637, 131919, 138515, 145441, 152714, 160350, 168368, 176787, 185627, 194909, 204655, 214888,
225633, 236915, 248761, 261200, 274261, 287975, 302374, 317493, 333368, 350037, 367539, 385916, 405212, 425473, 446747, 469085, 492540, 517168, 543027, 570179,
598688, 628623};

void InitDevice(){
}

int Answer(long long a, long long b){
	int l = a / SZ, r = l + tot[a % SZ] - 1;
	int L = b / SZ, R = L + tot[b % SZ] - 1;
	if(L <= l && r <= R){
		return 0;
	}
	if(l <= L && R <= r){
		return 1;
	}
	
	return 2;
}

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