oj.uz

Submission #564351

# Submission time Handle Problem Language Result Execution time Memory
564351 2022-05-19T03:21:20 Z blue City (JOI17_city) C++17
100 / 100
 474 ms 60832 KB 
#include "Encoder.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cassert>
using namespace std;
 
	namespace{
using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
 
 
const int abits = 19;
const int mx = (1<<abits);
using ll = long long;
using vll = vector<ll>;
 
int N;
vi edge[mx];
 
vll code(mx, 0);
 
vll dfsind(mx, 0);
vll subtree(mx, 1);
vll fakesubtree(mx, 1);
 
// int ct = -1;
 
 
 
 
 
 
 
vll getsizes()
{
	double base = 1.03;
	set<ll> res;
	res.insert(1);
 
	while(res.empty() || *res.rbegin() < mx)
	{
		ll curr = *res.rbegin();
		res.insert(max(curr+1, ll(curr*base)));
	}
 
	vll resvec;
	for(ll k : res)
		resvec.push_back(k);
 
	return resvec;
}
 
 
vll sizes;
 
 
 
void dfs(int u, int p, int firstind)
{
	// cerr << "dfs " << u << '\n';
	dfsind[u] = firstind;
	firstind++;
	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u, firstind);
		subtree[u] += subtree[v];
		firstind += subtree[v];
	}
 
	// if(dfsind[u] == 366)
		// cerr << u << " : " << subtree[u] << " -> ";
 
	auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]);
	assert(z != sizes.end() && *z >= subtree[u]);
	subtree[u] = *z;
	assert(subtree[u] <= mx);
	fakesubtree[u] = z - sizes.begin();
	
	// if(dfsind[u] == 366)
		// cerr << subtree[u] << '\n';
}
 
 
 
 
 
 
 
	}
 
 
void Encode(int N_, int A[], int B[])
{
	N = N_;
	sizes = getsizes();
 
	cerr << sz(sizes) << '\n';
 
	// for(int z : sizes)
	// 	cerr << z << ' ';
	// cerr << '\n';
 
 
 
	for(int e = 0; e < N-1; e++)
	{
		edge[A[e]].push_back(B[e]);
		edge[B[e]].push_back(A[e]);
	}
 
	// cerr << "done\n";
 
	dfs(0, -1, 0);
 
 
	// cerr << "done2\n";
 
	for(int i = 0; i < N; i++)
	{
		// cerr << i << " : " << dfsind[i] << ' ' << subtree[i] << ' ' << ((dfsind[i]<<18) | subtree[i]) << '\n';
		Code(i, (fakesubtree[i] << abits) | dfsind[i]);
	}
}
#include "Device.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
 
namespace
{
	using vi = vector<int>;
	using vvi = vector<vi>;
	using ll = long long;
	using vll = vector<ll>;
	#define sz(x) int(x.size())
 
	const int abits = 19;
	const int mx = (1<<abits);
 
	vll getsizes()
	{
		double base = 1.03;
		set<ll> res;
		res.insert(1);
 
		while(res.empty() || *res.rbegin() < mx)
		{
			ll curr = *res.rbegin();
			res.insert(max(curr+1, ll(curr*base)));
		}
	 
		vll resvec;
		for(ll k : res)
			resvec.push_back(k);
	 
		return resvec;
	}
 
 
	vll sizes;
 
}
 
void InitDevice()
{
	sizes = getsizes();
}
 
int Answer(long long S, long long T)
{
	// cerr << "query : " << S << ' ' << T << '\n';
// 
	// bool flag = 1;
	ll s_st = sizes[S>>abits];
	ll s_ind = S & ((1<<abits) - 1);
 
	ll t_st = sizes[T>>abits];
	ll t_ind = T & ((1<<abits) - 1);
 
 	// if(flag)
 	// {
 	// 	cerr << "bad query\n";
 	// 	cerr << "\n\n";
		// cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n";
		// cerr << (T>>18) << '\n';
 	// }
 	
	if(t_ind <= s_ind && s_ind < t_ind + t_st)
	{
		// if(flag)cerr << "case : 0\n";
		return 0;
	}
	else if(s_ind <= t_ind && t_ind < s_ind + s_st)
	{
		// if(flag)cerr << "case : 1\n";
		return 1;
	}
	else
	{
		// if(flag)cerr << "case : 2\n";
		return 2;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29492 KB Output is correct
2 Correct 16 ms 29516 KB Output is correct
3 Correct 17 ms 29364 KB Output is correct
4 Correct 14 ms 29392 KB Output is correct
5 Correct 17 ms 29576 KB Output is correct
6 Correct 14 ms 29580 KB Output is correct
7 Correct 15 ms 29512 KB Output is correct
8 Correct 14 ms 29576 KB Output is correct
9 Correct 15 ms 29392 KB Output is correct
10 Correct 20 ms 29372 KB Output is correct
11 Correct 19 ms 29204 KB Output is correct
12 Correct 14 ms 29424 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 37924 KB Output is correct - L = 81264640
2 Correct 204 ms 37880 KB Output is correct - L = 81264640
3 Correct 166 ms 37884 KB Output is correct - L = 80740352
4 Correct 180 ms 37956 KB Output is correct - L = 80740352
5 Correct 423 ms 59928 KB Output is correct - L = 187170816
6 Correct 421 ms 60044 KB Output is correct - L = 187170816
7 Correct 414 ms 60104 KB Output is correct - L = 187170816
8 Correct 463 ms 59672 KB Output is correct - L = 187170816
9 Correct 387 ms 60740 KB Output is correct - L = 192413696
10 Correct 372 ms 60712 KB Output is correct - L = 193986560
11 Correct 355 ms 60680 KB Output is correct - L = 193986560
12 Correct 342 ms 60832 KB Output is correct - L = 193986560
13 Correct 411 ms 60368 KB Output is correct - L = 189792256
14 Correct 448 ms 60244 KB Output is correct - L = 188219392
15 Correct 170 ms 37940 KB Output is correct - L = 81264640
16 Correct 182 ms 37964 KB Output is correct - L = 81264640
17 Correct 177 ms 37912 KB Output is correct - L = 81264640
18 Correct 388 ms 60148 KB Output is correct - L = 193462272
19 Correct 406 ms 60124 KB Output is correct - L = 193462272
20 Correct 420 ms 60328 KB Output is correct - L = 193462272
21 Correct 432 ms 60360 KB Output is correct - L = 192937984
22 Correct 474 ms 60076 KB Output is correct - L = 193462272
23 Correct 420 ms 60076 KB Output is correct - L = 193462272
24 Correct 395 ms 60188 KB Output is correct - L = 192937984
25 Correct 440 ms 60032 KB Output is correct - L = 192413696
26 Correct 449 ms 59964 KB Output is correct - L = 191889408
27 Correct 414 ms 59928 KB Output is correct - L = 190840832