oj.uz

Submission #563982

# Submission time Handle Problem Language Result Execution time Memory
563982 2022-05-18T10:19:50 Z blue City (JOI17_city) C++17
85 / 100
 2225 ms 74796 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 = 700'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.002755;
	set<ll> res;
	res.insert(1);
 
	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];
	}

	cerr << u << " : " << subtree[u] << " -> ";

	auto z = lower_bound(sizes.begin(), sizes.end(), (ll) subtree[u]);
	assert(z != sizes.end() && *z >= subtree[u]);
	subtree[u] = *z;
	assert(subtree[u] <= mx);
	fakesubtree[u] = z - sizes.begin();
	cerr << subtree[u] << '\n';
}
 
 
 
 
 
 
 
	}
 
 
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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.002755;
		set<ll> res;
		res.insert(1);
 
		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 19 ms 39516 KB Output is correct
2 Correct 19 ms 39348 KB Output is correct
3 Correct 18 ms 39500 KB Output is correct
4 Correct 20 ms 39496 KB Output is correct
5 Correct 21 ms 39644 KB Output is correct
6 Correct 19 ms 39448 KB Output is correct
7 Correct 19 ms 39516 KB Output is correct
8 Correct 18 ms 39492 KB Output is correct
9 Correct 18 ms 39480 KB Output is correct
10 Correct 19 ms 39516 KB Output is correct
11 Correct 20 ms 39428 KB Output is correct
12 Correct 19 ms 39516 KB Output is correct

Subtask #2
77.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 47936 KB Output is correct - L = 157548544
2 Correct 176 ms 47904 KB Output is correct - L = 157286400
3 Correct 176 ms 47980 KB Output is correct - L = 157548544
4 Correct 181 ms 47860 KB Output is correct - L = 157548544
5 Partially correct 2171 ms 74188 KB Output is partially correct - L = 718274560
6 Partially correct 2180 ms 74344 KB Output is partially correct - L = 718274560
7 Partially correct 2161 ms 74072 KB Output is partially correct - L = 718274560
8 Partially correct 2225 ms 73856 KB Output is partially correct - L = 717750272
9 Partially correct 2093 ms 74796 KB Output is partially correct - L = 720109568
10 Partially correct 2092 ms 74768 KB Output is partially correct - L = 721158144
11 Partially correct 2076 ms 74592 KB Output is partially correct - L = 721944576
12 Partially correct 2106 ms 74700 KB Output is partially correct - L = 721944576
13 Partially correct 2157 ms 74368 KB Output is partially correct - L = 719060992
14 Partially correct 2211 ms 74372 KB Output is partially correct - L = 718798848
15 Correct 180 ms 48004 KB Output is correct - L = 157548544
16 Correct 192 ms 47992 KB Output is correct - L = 157548544
17 Correct 181 ms 47820 KB Output is correct - L = 157548544
18 Partially correct 2194 ms 74104 KB Output is partially correct - L = 721682432
19 Partially correct 2105 ms 74296 KB Output is partially correct - L = 721682432
20 Partially correct 2148 ms 74448 KB Output is partially correct - L = 721682432
21 Partially correct 2195 ms 74192 KB Output is partially correct - L = 720109568
22 Partially correct 2174 ms 74620 KB Output is partially correct - L = 721420288
23 Partially correct 2118 ms 74024 KB Output is partially correct - L = 721420288
24 Partially correct 2145 ms 74036 KB Output is partially correct - L = 721158144
25 Partially correct 2137 ms 74316 KB Output is partially correct - L = 721158144
26 Partially correct 2209 ms 74400 KB Output is partially correct - L = 720896000
27 Partially correct 2168 ms 73972 KB Output is partially correct - L = 720371712