oj.uz

Submission #563936

# Submission time Handle Problem Language Result Execution time Memory
563936 2022-05-18T09:50:22 Z blue City (JOI17_city) C++17
8 / 100
 447 ms 45448 KB 
#include "Encoder.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
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.001;
	set<ll> res;

	double curr = 1;
	while(curr <= 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]);
	subtree[u] = *z;
	fakesubtree[u] = z - sizes.begin();
}







	}


void Encode(int N_, int A[], int B[])
{
	N = N_;
	sizes = getsizes();

	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.001;
		set<ll> res;

		double curr = 1;
		while(curr <= 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 10 ms 15280 KB Output is correct
2 Correct 10 ms 15280 KB Output is correct
3 Correct 9 ms 15280 KB Output is correct
4 Correct 12 ms 15276 KB Output is correct
5 Correct 10 ms 15276 KB Output is correct
6 Correct 10 ms 15272 KB Output is correct
7 Correct 17 ms 15276 KB Output is correct
8 Correct 9 ms 15276 KB Output is correct
9 Correct 9 ms 15276 KB Output is correct
10 Correct 12 ms 15256 KB Output is correct
11 Correct 10 ms 15284 KB Output is correct
12 Correct 10 ms 15272 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 23676 KB Output is correct - L = 183238656
2 Correct 195 ms 23620 KB Output is correct - L = 182976512
3 Correct 195 ms 23640 KB Output is correct - L = 183238656
4 Correct 178 ms 23692 KB Output is correct - L = 183238656
5 Incorrect 447 ms 45448 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -