oj.uz

Submission #563965

# Submission time Handle Problem Language Result Execution time Memory
563965 2022-05-18T10:06:15 Z blue City (JOI17_city) C++17
85 / 100
 516 ms 70648 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.0026;
	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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.0026;
		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 18 ms 39516 KB Output is correct
2 Correct 18 ms 39284 KB Output is correct
3 Correct 19 ms 39428 KB Output is correct
4 Correct 19 ms 39468 KB Output is correct
5 Correct 20 ms 39344 KB Output is correct
6 Correct 18 ms 39512 KB Output is correct
7 Correct 19 ms 39520 KB Output is correct
8 Correct 19 ms 39432 KB Output is correct
9 Correct 18 ms 39452 KB Output is correct
10 Correct 21 ms 39496 KB Output is correct
11 Correct 19 ms 39512 KB Output is correct
12 Correct 20 ms 39444 KB Output is correct

Subtask #2
77.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 47908 KB Output is correct - L = 160956416
2 Correct 177 ms 47920 KB Output is correct - L = 160956416
3 Correct 178 ms 48020 KB Output is correct - L = 160956416
4 Correct 186 ms 47848 KB Output is correct - L = 160956416
5 Partially correct 387 ms 69940 KB Output is partially correct - L = 755236864
6 Partially correct 393 ms 70048 KB Output is partially correct - L = 755236864
7 Partially correct 417 ms 69912 KB Output is partially correct - L = 755236864
8 Partially correct 401 ms 69508 KB Output is partially correct - L = 754712576
9 Partially correct 351 ms 70648 KB Output is partially correct - L = 756809728
10 Partially correct 342 ms 70520 KB Output is partially correct - L = 757858304
11 Partially correct 344 ms 70496 KB Output is partially correct - L = 758906880
12 Partially correct 345 ms 70568 KB Output is partially correct - L = 758906880
13 Partially correct 368 ms 70276 KB Output is partially correct - L = 756285440
14 Partially correct 432 ms 70068 KB Output is partially correct - L = 755761152
15 Correct 185 ms 47880 KB Output is correct - L = 160956416
16 Correct 178 ms 48032 KB Output is correct - L = 160956416
17 Correct 220 ms 47864 KB Output is correct - L = 160956416
18 Partially correct 446 ms 70332 KB Output is partially correct - L = 758644736
19 Partially correct 435 ms 69988 KB Output is partially correct - L = 758644736
20 Partially correct 413 ms 70112 KB Output is partially correct - L = 758644736
21 Partially correct 417 ms 70028 KB Output is partially correct - L = 757334016
22 Partially correct 493 ms 70060 KB Output is partially correct - L = 758382592
23 Partially correct 445 ms 70028 KB Output is partially correct - L = 758382592
24 Partially correct 506 ms 69844 KB Output is partially correct - L = 758382592
25 Partially correct 502 ms 69876 KB Output is partially correct - L = 758120448
26 Partially correct 516 ms 69764 KB Output is partially correct - L = 757858304
27 Partially correct 471 ms 69696 KB Output is partially correct - L = 757334016