oj.uz

Submission #564346

# Submission time Handle Problem Language Result Execution time Memory
564346 2022-05-19T03:18:48 Z blue City (JOI17_city) C++17
80 / 100
 455 ms 90352 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 abits = 20;
const int mx = (1<<abits);
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.01;
	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] << abits) | 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 abits = 20;
	const int mx = (1<<abits);
 
	vll getsizes()
	{
		double base = 1.01;
		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>>abits];
	ll s_ind = S & ((1<<abits) - 1);
 
	ll t_st = sizes[T>>abits];
	ll t_ind = T & ((1<<abits) - 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 26 ms 58164 KB Output is correct
2 Correct 27 ms 58192 KB Output is correct
3 Correct 29 ms 58320 KB Output is correct
4 Correct 28 ms 58352 KB Output is correct
5 Correct 31 ms 58336 KB Output is correct
6 Correct 27 ms 58372 KB Output is correct
7 Correct 29 ms 58352 KB Output is correct
8 Correct 27 ms 58356 KB Output is correct
9 Correct 26 ms 58360 KB Output is correct
10 Correct 27 ms 58380 KB Output is correct
11 Correct 27 ms 58328 KB Output is correct
12 Correct 27 ms 58404 KB Output is correct

Subtask #2
72.0 / 92.0

# Verdict Execution time Memory Grader output
1 Partially correct 203 ms 67816 KB Output is partially correct - L = 362807296
2 Partially correct 185 ms 67816 KB Output is partially correct - L = 362807296
3 Partially correct 186 ms 67780 KB Output is partially correct - L = 361758720
4 Partially correct 182 ms 67788 KB Output is partially correct - L = 361758720
5 Partially correct 409 ms 89568 KB Output is partially correct - L = 991952896
6 Partially correct 410 ms 89360 KB Output is partially correct - L = 991952896
7 Partially correct 409 ms 89556 KB Output is partially correct - L = 990904320
8 Partially correct 409 ms 89100 KB Output is partially correct - L = 993001472
9 Partially correct 359 ms 90048 KB Output is partially correct - L = 999292928
10 Partially correct 352 ms 90352 KB Output is partially correct - L = 1005584384
11 Partially correct 343 ms 90032 KB Output is partially correct - L = 1006632960
12 Partially correct 337 ms 90160 KB Output is partially correct - L = 1006632960
13 Partially correct 376 ms 89660 KB Output is partially correct - L = 997195776
14 Partially correct 391 ms 89484 KB Output is partially correct - L = 994050048
15 Partially correct 187 ms 67172 KB Output is partially correct - L = 361758720
16 Partially correct 180 ms 67008 KB Output is partially correct - L = 362807296
17 Partially correct 177 ms 66948 KB Output is partially correct - L = 361758720
18 Partially correct 386 ms 89784 KB Output is partially correct - L = 1005584384
19 Partially correct 393 ms 89580 KB Output is partially correct - L = 1005584384
20 Partially correct 391 ms 89080 KB Output is partially correct - L = 1005584384
21 Partially correct 395 ms 89232 KB Output is partially correct - L = 1001390080
22 Partially correct 401 ms 89024 KB Output is partially correct - L = 1004535808
23 Partially correct 392 ms 88876 KB Output is partially correct - L = 1004535808
24 Partially correct 455 ms 89132 KB Output is partially correct - L = 1003487232
25 Partially correct 445 ms 88852 KB Output is partially correct - L = 1002438656
26 Partially correct 432 ms 88892 KB Output is partially correct - L = 1001390080
27 Partially correct 430 ms 88760 KB Output is partially correct - L = 1000341504