oj.uz

Submission #564288

# Submission time Handle Problem Language Result Execution time Memory
564288 2022-05-18T20:03:00 Z blue City (JOI17_city) C++17
94 / 100
 438 ms 76032 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.006;
	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.006;
		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 20 ms 44720 KB Output is correct
2 Correct 20 ms 44752 KB Output is correct
3 Correct 20 ms 44780 KB Output is correct
4 Correct 23 ms 44968 KB Output is correct
5 Correct 21 ms 44752 KB Output is correct
6 Correct 26 ms 44600 KB Output is correct
7 Correct 22 ms 44516 KB Output is correct
8 Correct 20 ms 44568 KB Output is correct
9 Correct 21 ms 44696 KB Output is correct
10 Correct 22 ms 44572 KB Output is correct
11 Correct 22 ms 44596 KB Output is correct
12 Correct 21 ms 44752 KB Output is correct

Subtask #2
86.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 53188 KB Output is correct - L = 126091264
2 Correct 176 ms 53100 KB Output is correct - L = 126091264
3 Correct 211 ms 53144 KB Output is correct - L = 125829120
4 Correct 180 ms 53156 KB Output is correct - L = 125829120
5 Partially correct 436 ms 75092 KB Output is partially correct - L = 389808128
6 Partially correct 409 ms 75196 KB Output is partially correct - L = 389808128
7 Partially correct 438 ms 75180 KB Output is partially correct - L = 389808128
8 Partially correct 435 ms 74792 KB Output is partially correct - L = 390332416
9 Partially correct 351 ms 75800 KB Output is partially correct - L = 392167424
10 Partially correct 400 ms 76032 KB Output is partially correct - L = 393216000
11 Partially correct 336 ms 75892 KB Output is partially correct - L = 393478144
12 Partially correct 355 ms 75816 KB Output is partially correct - L = 393478144
13 Partially correct 378 ms 75552 KB Output is partially correct - L = 391118848
14 Partially correct 402 ms 75280 KB Output is partially correct - L = 390594560
15 Correct 186 ms 53120 KB Output is correct - L = 126091264
16 Correct 167 ms 53260 KB Output is correct - L = 126091264
17 Correct 194 ms 53156 KB Output is correct - L = 126091264
18 Partially correct 384 ms 75568 KB Output is partially correct - L = 393216000
19 Partially correct 384 ms 75440 KB Output is partially correct - L = 393216000
20 Partially correct 382 ms 75468 KB Output is partially correct - L = 393216000
21 Partially correct 377 ms 75480 KB Output is partially correct - L = 391905280
22 Partially correct 411 ms 75344 KB Output is partially correct - L = 393216000
23 Partially correct 397 ms 75348 KB Output is partially correct - L = 393216000
24 Partially correct 399 ms 75292 KB Output is partially correct - L = 392953856
25 Partially correct 403 ms 75200 KB Output is partially correct - L = 392691712
26 Partially correct 412 ms 75296 KB Output is partially correct - L = 392429568
27 Partially correct 435 ms 75232 KB Output is partially correct - L = 391905280