oj.uz

Submission #563959

# Submission time Handle Problem Language Result Execution time Memory
563959 2022-05-18T10:03:16 Z blue City (JOI17_city) C++17
83 / 100
 436 ms 51488 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.0023;
	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.0023;
		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 9 ms 20284 KB Output is correct
2 Correct 11 ms 20336 KB Output is correct
3 Correct 9 ms 20252 KB Output is correct
4 Correct 9 ms 20276 KB Output is correct
5 Correct 11 ms 20280 KB Output is correct
6 Correct 11 ms 20276 KB Output is correct
7 Correct 9 ms 20284 KB Output is correct
8 Correct 11 ms 20244 KB Output is correct
9 Correct 9 ms 20304 KB Output is correct
10 Correct 11 ms 20276 KB Output is correct
11 Correct 11 ms 20280 KB Output is correct
12 Correct 11 ms 20280 KB Output is correct

Subtask #2
75.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 28800 KB Output is correct - L = 168296448
2 Correct 176 ms 28812 KB Output is correct - L = 167772160
3 Correct 169 ms 28696 KB Output is correct - L = 168034304
4 Correct 169 ms 28700 KB Output is correct - L = 168034304
5 Partially correct 398 ms 50832 KB Output is partially correct - L = 839647232
6 Partially correct 388 ms 50676 KB Output is partially correct - L = 839647232
7 Partially correct 395 ms 50896 KB Output is partially correct - L = 839385088
8 Partially correct 402 ms 50524 KB Output is partially correct - L = 839385088
9 Partially correct 335 ms 51308 KB Output is partially correct - L = 841482240
10 Partially correct 324 ms 51384 KB Output is partially correct - L = 842006528
11 Partially correct 322 ms 51360 KB Output is partially correct - L = 843055104
12 Partially correct 327 ms 51488 KB Output is partially correct - L = 843317248
13 Partially correct 362 ms 51044 KB Output is partially correct - L = 840433664
14 Partially correct 388 ms 50788 KB Output is partially correct - L = 839647232
15 Correct 180 ms 28816 KB Output is correct - L = 168034304
16 Correct 168 ms 28672 KB Output is correct - L = 168034304
17 Correct 173 ms 28692 KB Output is correct - L = 168034304
18 Partially correct 379 ms 50904 KB Output is partially correct - L = 843055104
19 Partially correct 378 ms 51128 KB Output is partially correct - L = 843055104
20 Partially correct 371 ms 50868 KB Output is partially correct - L = 843055104
21 Partially correct 382 ms 50948 KB Output is partially correct - L = 841482240
22 Partially correct 411 ms 50860 KB Output is partially correct - L = 842792960
23 Partially correct 386 ms 50784 KB Output is partially correct - L = 842792960
24 Partially correct 413 ms 50748 KB Output is partially correct - L = 842530816
25 Partially correct 403 ms 50756 KB Output is partially correct - L = 842268672
26 Partially correct 436 ms 50816 KB Output is partially correct - L = 842006528
27 Partially correct 425 ms 50720 KB Output is partially correct - L = 841744384