oj.uz

Submission #563950

# Submission time Handle Problem Language Result Execution time Memory
563950 2022-05-18T09:58:02 Z blue City (JOI17_city) C++17
8 / 100
 206 ms 53316 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 = 250'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 = 250'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 26 ms 19604 KB Output is correct
2 Correct 27 ms 19732 KB Output is correct
3 Correct 26 ms 19628 KB Output is correct
4 Correct 31 ms 19604 KB Output is correct
5 Correct 26 ms 19608 KB Output is correct
6 Correct 26 ms 19628 KB Output is correct
7 Correct 26 ms 19608 KB Output is correct
8 Correct 27 ms 19680 KB Output is correct
9 Correct 28 ms 19624 KB Output is correct
10 Correct 32 ms 19552 KB Output is correct
11 Correct 28 ms 19604 KB Output is correct
12 Correct 30 ms 19452 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 27756 KB Output is correct - L = 183238656
2 Correct 203 ms 27764 KB Output is correct - L = 182976512
3 Correct 179 ms 27636 KB Output is correct - L = 183238656
4 Correct 185 ms 27668 KB Output is correct - L = 183238656
5 Runtime error 206 ms 53316 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -