oj.uz

Submission #564287

# Submission time Handle Problem Language Result Execution time Memory
564287 2022-05-18T20:02:16 Z blue City (JOI17_city) C++17
92 / 100
 468 ms 75860 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 = 800'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.005;
	set<ll> res;
	res.insert(1);

	while(res.empty() || *res.rbegin() < mx)
	{
		ll curr = *res.rbegin();
		res.insert(max(curr+1, ll(curr*base)));
	}
 
	vll resvec;
	for(ll k : res)
		resvec.push_back(k);
 
	return resvec;
}
 
 
vll sizes;
 
 
 
void dfs(int u, int p, int firstind)
{
	// cerr << "dfs " << u << '\n';
	dfsind[u] = firstind;
	firstind++;
	for(int v : edge[u])
	{
		if(v == p) continue;
		dfs(v, u, firstind);
		subtree[u] += subtree[v];
		firstind += subtree[v];
	}
 
	// if(dfsind[u] == 366)
		// 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();
	
	// if(dfsind[u] == 366)
		// 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, 0);
 
 
	// 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 = 800'000;
 
	vll getsizes()
	{
		double base = 1.005;
		set<ll> res;
		res.insert(1);

		while(res.empty() || *res.rbegin() < mx)
		{
			ll curr = *res.rbegin();
			res.insert(max(curr+1, ll(curr*base)));
		}
	 
		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)
{
	// cerr << "query : " << S << ' ' << T << '\n';
// 
	// bool flag = 1;
	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);
 
 	// if(flag)
 	// {
 	// 	cerr << "bad query\n";
 	// 	cerr << "\n\n";
		// cerr << S << ' ' << T << " : " << s_ind << ' ' << s_st << " | " << t_ind << ' ' << t_st << "\n";
		// cerr << (T>>18) << '\n';
 	// }
 	
	if(t_ind <= s_ind && s_ind < t_ind + t_st)
	{
		// if(flag)cerr << "case : 0\n";
		return 0;
	}
	else if(s_ind <= t_ind && t_ind < s_ind + s_st)
	{
		// if(flag)cerr << "case : 1\n";
		return 1;
	}
	else
	{
		// if(flag)cerr << "case : 2\n";
		return 2;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44756 KB Output is correct
2 Correct 28 ms 44736 KB Output is correct
3 Correct 21 ms 44740 KB Output is correct
4 Correct 21 ms 44792 KB Output is correct
5 Correct 20 ms 44772 KB Output is correct
6 Correct 20 ms 44768 KB Output is correct
7 Correct 20 ms 44780 KB Output is correct
8 Correct 20 ms 44716 KB Output is correct
9 Correct 21 ms 44752 KB Output is correct
10 Correct 26 ms 44772 KB Output is correct
11 Correct 22 ms 44764 KB Output is correct
12 Correct 21 ms 44772 KB Output is correct

Subtask #2
84.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 53164 KB Output is correct - L = 139984896
2 Correct 178 ms 53160 KB Output is correct - L = 139722752
3 Correct 183 ms 53244 KB Output is correct - L = 139722752
4 Correct 178 ms 53300 KB Output is correct - L = 139984896
5 Partially correct 396 ms 75216 KB Output is partially correct - L = 457965568
6 Partially correct 468 ms 75236 KB Output is partially correct - L = 457965568
7 Partially correct 400 ms 75308 KB Output is partially correct - L = 457965568
8 Partially correct 440 ms 74996 KB Output is partially correct - L = 458752000
9 Partially correct 345 ms 75856 KB Output is partially correct - L = 459538432
10 Partially correct 370 ms 75856 KB Output is partially correct - L = 461373440
11 Partially correct 373 ms 75844 KB Output is partially correct - L = 461635584
12 Partially correct 350 ms 75860 KB Output is partially correct - L = 461897728
13 Partially correct 393 ms 75664 KB Output is partially correct - L = 459276288
14 Partially correct 415 ms 75344 KB Output is partially correct - L = 458489856
15 Correct 202 ms 53232 KB Output is correct - L = 139984896
16 Correct 172 ms 53284 KB Output is correct - L = 139984896
17 Correct 197 ms 53156 KB Output is correct - L = 139722752
18 Partially correct 384 ms 75468 KB Output is partially correct - L = 461635584
19 Partially correct 406 ms 75568 KB Output is partially correct - L = 461635584
20 Partially correct 437 ms 75512 KB Output is partially correct - L = 461635584
21 Partially correct 426 ms 75492 KB Output is partially correct - L = 460587008
22 Partially correct 388 ms 75384 KB Output is partially correct - L = 461373440
23 Partially correct 435 ms 75468 KB Output is partially correct - L = 461373440
24 Partially correct 437 ms 75332 KB Output is partially correct - L = 461111296
25 Partially correct 461 ms 75272 KB Output is partially correct - L = 460849152
26 Partially correct 456 ms 75424 KB Output is partially correct - L = 460849152
27 Partially correct 411 ms 75336 KB Output is partially correct - L = 460324864