oj.uz

Submission #563957

# Submission time Handle Problem Language Result Execution time Memory
563957 2022-05-18T10:01:37 Z blue City (JOI17_city) C++17
8 / 100
 185 ms 58524 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 = 900'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.012;
	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();
	assert(subtree[u] <= mx);
}







	}


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 = 900'000;

	vll getsizes()
	{
		double base = 1.012;
		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 21 ms 50136 KB Output is correct
2 Correct 25 ms 50176 KB Output is correct
3 Correct 23 ms 50144 KB Output is correct
4 Correct 26 ms 50132 KB Output is correct
5 Correct 22 ms 49972 KB Output is correct
6 Correct 23 ms 50144 KB Output is correct
7 Correct 22 ms 50212 KB Output is correct
8 Correct 21 ms 50172 KB Output is correct
9 Correct 23 ms 50076 KB Output is correct
10 Correct 23 ms 50184 KB Output is correct
11 Correct 22 ms 50172 KB Output is correct
12 Correct 21 ms 50152 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 58460 KB Output is correct - L = 68419584
2 Incorrect 185 ms 58524 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -