oj.uz

Submission #563952

# Submission time Handle Problem Language Result Execution time Memory
563952 2022-05-18T09:59:14 Z blue City (JOI17_city) C++17
73 / 100
 511 ms 51656 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.001;
	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.001;
		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 12 ms 20804 KB Output is correct
2 Correct 13 ms 20796 KB Output is correct
3 Correct 13 ms 20740 KB Output is correct
4 Correct 12 ms 20792 KB Output is correct
5 Correct 13 ms 20792 KB Output is correct
6 Correct 12 ms 20800 KB Output is correct
7 Correct 14 ms 20788 KB Output is correct
8 Correct 13 ms 20796 KB Output is correct
9 Correct 13 ms 20792 KB Output is correct
10 Correct 15 ms 20772 KB Output is correct
11 Correct 12 ms 20792 KB Output is correct
12 Correct 12 ms 20792 KB Output is correct

Subtask #2
65.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 29196 KB Output is correct - L = 183238656
2 Correct 185 ms 29208 KB Output is correct - L = 182976512
3 Correct 178 ms 29124 KB Output is correct - L = 183238656
4 Correct 184 ms 29104 KB Output is correct - L = 183238656
5 Partially correct 432 ms 50804 KB Output is partially correct - L = 1710489600
6 Partially correct 442 ms 50856 KB Output is partially correct - L = 1710489600
7 Partially correct 446 ms 50988 KB Output is partially correct - L = 1710489600
8 Partially correct 511 ms 50600 KB Output is partially correct - L = 1710751744
9 Partially correct 389 ms 51516 KB Output is partially correct - L = 1712062464
10 Partially correct 366 ms 51608 KB Output is partially correct - L = 1713111040
11 Partially correct 369 ms 51656 KB Output is partially correct - L = 1714159616
12 Partially correct 368 ms 51520 KB Output is partially correct - L = 1714421760
13 Partially correct 466 ms 51224 KB Output is partially correct - L = 1711538176
14 Partially correct 430 ms 51040 KB Output is partially correct - L = 1711013888
15 Correct 183 ms 29208 KB Output is correct - L = 183238656
16 Correct 192 ms 29192 KB Output is correct - L = 183238656
17 Correct 181 ms 29140 KB Output is correct - L = 183238656
18 Partially correct 441 ms 51180 KB Output is partially correct - L = 1714159616
19 Partially correct 414 ms 51132 KB Output is partially correct - L = 1714159616
20 Partially correct 419 ms 51084 KB Output is partially correct - L = 1714159616
21 Partially correct 392 ms 51156 KB Output is partially correct - L = 1712586752
22 Partially correct 388 ms 51040 KB Output is partially correct - L = 1713897472
23 Partially correct 385 ms 51008 KB Output is partially correct - L = 1713897472
24 Partially correct 391 ms 51024 KB Output is partially correct - L = 1713897472
25 Partially correct 403 ms 50960 KB Output is partially correct - L = 1713373184
26 Partially correct 414 ms 51200 KB Output is partially correct - L = 1713111040
27 Partially correct 398 ms 50896 KB Output is partially correct - L = 1712848896