oj.uz

Submission #563958

# Submission time Handle Problem Language Result Execution time Memory
563958 2022-05-18T10:02:33 Z blue City (JOI17_city) C++17
78 / 100
 413 ms 51888 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.0015;
	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.0015;
		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 20532 KB Output is correct
2 Correct 11 ms 20540 KB Output is correct
3 Correct 12 ms 20684 KB Output is correct
4 Correct 12 ms 20544 KB Output is correct
5 Correct 9 ms 20540 KB Output is correct
6 Correct 11 ms 20472 KB Output is correct
7 Correct 11 ms 20540 KB Output is correct
8 Correct 11 ms 20536 KB Output is correct
9 Correct 11 ms 20548 KB Output is correct
10 Correct 11 ms 20532 KB Output is correct
11 Correct 13 ms 20812 KB Output is correct
12 Correct 11 ms 20536 KB Output is correct

Subtask #2
70.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 28944 KB Output is correct - L = 182976512
2 Correct 167 ms 28948 KB Output is correct - L = 182714368
3 Correct 172 ms 29124 KB Output is correct - L = 182976512
4 Correct 165 ms 28980 KB Output is correct - L = 182976512
5 Partially correct 392 ms 50948 KB Output is partially correct - L = 1211629568
6 Partially correct 384 ms 50832 KB Output is partially correct - L = 1211891712
7 Partially correct 388 ms 50968 KB Output is partially correct - L = 1211629568
8 Partially correct 389 ms 50544 KB Output is partially correct - L = 1211891712
9 Partially correct 333 ms 51428 KB Output is partially correct - L = 1213988864
10 Partially correct 340 ms 51888 KB Output is partially correct - L = 1214251008
11 Partially correct 322 ms 51484 KB Output is partially correct - L = 1215299584
12 Partially correct 336 ms 51608 KB Output is partially correct - L = 1215561728
13 Partially correct 376 ms 51148 KB Output is partially correct - L = 1212678144
14 Partially correct 382 ms 51012 KB Output is partially correct - L = 1212153856
15 Correct 170 ms 29112 KB Output is correct - L = 182976512
16 Correct 166 ms 28912 KB Output is correct - L = 182976512
17 Correct 167 ms 28916 KB Output is correct - L = 182976512
18 Partially correct 382 ms 51020 KB Output is partially correct - L = 1215299584
19 Partially correct 375 ms 51100 KB Output is partially correct - L = 1215299584
20 Partially correct 372 ms 51252 KB Output is partially correct - L = 1215299584
21 Partially correct 375 ms 51092 KB Output is partially correct - L = 1213464576
22 Partially correct 369 ms 50980 KB Output is partially correct - L = 1215037440
23 Partially correct 413 ms 50980 KB Output is partially correct - L = 1215037440
24 Partially correct 389 ms 50912 KB Output is partially correct - L = 1214775296
25 Partially correct 406 ms 50868 KB Output is partially correct - L = 1214513152
26 Partially correct 404 ms 51036 KB Output is partially correct - L = 1214513152
27 Partially correct 397 ms 50700 KB Output is partially correct - L = 1213726720