oj.uz

Submission #700127

# Submission time Handle Problem Language Result Execution time Memory
700127 2023-02-18T16:35:14 Z amunduzbaev City (JOI17_city) C++17
100 / 100
 458 ms 47824 KB 
#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]);
	}
}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 528 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 524 KB Output is correct
5 Correct 0 ms 520 KB Output is correct
6 Correct 0 ms 524 KB Output is correct
7 Correct 2 ms 516 KB Output is correct
8 Correct 1 ms 528 KB Output is correct
9 Correct 1 ms 524 KB Output is correct
10 Correct 0 ms 524 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 528 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 14496 KB Output is correct - L = 168588
2 Correct 163 ms 16056 KB Output is correct - L = 170372
3 Correct 147 ms 16280 KB Output is correct - L = 164574
4 Correct 163 ms 16160 KB Output is correct - L = 164128
5 Correct 382 ms 47612 KB Output is correct - L = 67063459
6 Correct 409 ms 47552 KB Output is correct - L = 69311522
7 Correct 456 ms 47616 KB Output is correct - L = 68533921
8 Correct 402 ms 47468 KB Output is correct - L = 77820533
9 Correct 344 ms 47584 KB Output is correct - L = 111055338
10 Correct 325 ms 47488 KB Output is correct - L = 109872546
11 Correct 348 ms 47692 KB Output is correct - L = 127150140
12 Correct 377 ms 47596 KB Output is correct - L = 115330025
13 Correct 373 ms 47584 KB Output is correct - L = 89013349
14 Correct 397 ms 47516 KB Output is correct - L = 72911188
15 Correct 148 ms 16100 KB Output is correct - L = 166804
16 Correct 161 ms 16168 KB Output is correct - L = 169926
17 Correct 155 ms 16104 KB Output is correct - L = 163013
18 Correct 372 ms 47232 KB Output is correct - L = 121095690
19 Correct 373 ms 47328 KB Output is correct - L = 55749777
20 Correct 393 ms 47120 KB Output is correct - L = 55749777
21 Correct 458 ms 47400 KB Output is correct - L = 115329802
22 Correct 379 ms 47640 KB Output is correct - L = 56148724
23 Correct 421 ms 47316 KB Output is correct - L = 56299249
24 Correct 441 ms 47492 KB Output is correct - L = 57164489
25 Correct 416 ms 47276 KB Output is correct - L = 57416033
26 Correct 391 ms 47664 KB Output is correct - L = 58126511
27 Correct 412 ms 47824 KB Output is correct - L = 58317399