oj.uz

Submission #563951

# Submission time Handle Problem Language Result Execution time Memory
563951 2022-05-18T09:58:54 Z blue City (JOI17_city) C++17
46 / 100
 434 ms 54200 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 mx = 350'000;
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.0001;
	set<ll> res;

	double curr = 1;
	while(res.empty() || *res.rbegin() < mx)
	{
		curr *= base;
		res.insert(curr);
	}

	vll resvec;
	for(ll k : res)
		resvec.push_back(k);

	return resvec;
}


vll sizes;



void dfs(int u, int p)
{
	// cerr << "dfs " << u << '\n';
	dfsind[u] = ++ct;
	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u);
		subtree[u] += subtree[v];
	}
	auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]);
	assert(z != sizes.end() && *z >= subtree[u]);
	subtree[u] = *z;
	fakesubtree[u] = z - sizes.begin();
}







	}


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);


	// 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] << 18) | 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 mx = 350'000;

	vll getsizes()
	{
		double base = 1.0001;
		set<ll> res;

		double curr = 1;
		while(res.empty() || *res.rbegin() < mx)
		{
			curr *= base;
			res.insert(curr);
		}

		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)
{
	ll s_st = sizes[S>>18];
	ll s_ind = S & ((1<<18) - 1);

	ll t_st = sizes[T>>18];
	ll t_ind = T & ((1<<18) - 1);

	// cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n";

	if(t_ind <= s_ind && s_ind + s_st <= t_ind + t_st)
		return 0;
	else if(s_ind <= t_ind && t_ind + t_st <= s_ind + s_st)
		return 1;
	else
		return 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25376 KB Output is correct
2 Correct 33 ms 25348 KB Output is correct
3 Correct 31 ms 25272 KB Output is correct
4 Correct 32 ms 25400 KB Output is correct
5 Correct 30 ms 25320 KB Output is correct
6 Correct 33 ms 25256 KB Output is correct
7 Correct 31 ms 25332 KB Output is correct
8 Correct 31 ms 25284 KB Output is correct
9 Correct 28 ms 25360 KB Output is correct
10 Correct 30 ms 25508 KB Output is correct
11 Correct 34 ms 25436 KB Output is correct
12 Correct 31 ms 25400 KB Output is correct

Subtask #2
38.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 33544 KB Output is correct - L = 183238656
2 Correct 187 ms 33612 KB Output is correct - L = 182976512
3 Correct 189 ms 33544 KB Output is correct - L = 183238656
4 Correct 188 ms 33476 KB Output is correct - L = 183238656
5 Partially correct 418 ms 53484 KB Output is partially correct - L = 11059855360
6 Partially correct 421 ms 53484 KB Output is partially correct - L = 11059855360
7 Partially correct 412 ms 53376 KB Output is partially correct - L = 11059855360
8 Partially correct 410 ms 53112 KB Output is partially correct - L = 11059593216
9 Partially correct 351 ms 54064 KB Output is partially correct - L = 11061952512
10 Partially correct 357 ms 54144 KB Output is partially correct - L = 11061428224
11 Partially correct 376 ms 54200 KB Output is partially correct - L = 11062214656
12 Partially correct 353 ms 54100 KB Output is partially correct - L = 11063525376
13 Partially correct 387 ms 53852 KB Output is partially correct - L = 11061166080
14 Partially correct 408 ms 53644 KB Output is partially correct - L = 11060379648
15 Correct 191 ms 33504 KB Output is correct - L = 183238656
16 Correct 199 ms 33540 KB Output is correct - L = 183238656
17 Correct 195 ms 33524 KB Output is correct - L = 183238656
18 Partially correct 383 ms 53608 KB Output is partially correct - L = 11063001088
19 Partially correct 398 ms 53656 KB Output is partially correct - L = 11063525376
20 Partially correct 390 ms 53608 KB Output is partially correct - L = 11063525376
21 Partially correct 416 ms 53612 KB Output is partially correct - L = 11061690368
22 Partially correct 424 ms 53596 KB Output is partially correct - L = 11063263232
23 Partially correct 407 ms 53628 KB Output is partially correct - L = 11063525376
24 Partially correct 416 ms 53616 KB Output is partially correct - L = 11063263232
25 Partially correct 424 ms 53732 KB Output is partially correct - L = 11063001088
26 Partially correct 421 ms 53508 KB Output is partially correct - L = 11062738944
27 Partially correct 434 ms 53276 KB Output is partially correct - L = 11062214656