oj.uz

Submission #564286

# Submission time Handle Problem Language Result Execution time Memory
564286 2022-05-18T20:01:55 Z blue City (JOI17_city) C++17
85 / 100
 482 ms 76176 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.003;
	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.003;
		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 45032 KB Output is correct
2 Correct 21 ms 44944 KB Output is correct
3 Correct 22 ms 44952 KB Output is correct
4 Correct 24 ms 44896 KB Output is correct
5 Correct 24 ms 44824 KB Output is correct
6 Correct 22 ms 45028 KB Output is correct
7 Correct 20 ms 44940 KB Output is correct
8 Correct 24 ms 45024 KB Output is correct
9 Correct 26 ms 45016 KB Output is correct
10 Correct 23 ms 44984 KB Output is correct
11 Correct 20 ms 45008 KB Output is correct
12 Correct 22 ms 44916 KB Output is correct

Subtask #2
77.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 53328 KB Output is correct - L = 179044352
2 Correct 182 ms 53300 KB Output is correct - L = 178782208
3 Correct 187 ms 53468 KB Output is correct - L = 179044352
4 Correct 180 ms 53336 KB Output is correct - L = 179044352
5 Partially correct 482 ms 75344 KB Output is partially correct - L = 717488128
6 Partially correct 437 ms 75296 KB Output is partially correct - L = 717750272
7 Partially correct 426 ms 75332 KB Output is partially correct - L = 717488128
8 Partially correct 402 ms 75080 KB Output is partially correct - L = 718012416
9 Partially correct 375 ms 75980 KB Output is partially correct - L = 719323136
10 Partially correct 363 ms 76052 KB Output is partially correct - L = 720633856
11 Partially correct 345 ms 75932 KB Output is partially correct - L = 721420288
12 Partially correct 353 ms 76176 KB Output is partially correct - L = 721420288
13 Partially correct 429 ms 75676 KB Output is partially correct - L = 718798848
14 Partially correct 425 ms 75524 KB Output is partially correct - L = 718274560
15 Correct 179 ms 53372 KB Output is correct - L = 179044352
16 Correct 176 ms 53304 KB Output is correct - L = 179044352
17 Correct 181 ms 53460 KB Output is correct - L = 179044352
18 Partially correct 397 ms 75676 KB Output is partially correct - L = 721158144
19 Partially correct 401 ms 75552 KB Output is partially correct - L = 721158144
20 Partially correct 418 ms 75580 KB Output is partially correct - L = 721158144
21 Partially correct 430 ms 75560 KB Output is partially correct - L = 719585280
22 Partially correct 404 ms 75476 KB Output is partially correct - L = 720896000
23 Partially correct 433 ms 75512 KB Output is partially correct - L = 720896000
24 Partially correct 430 ms 75560 KB Output is partially correct - L = 720633856
25 Partially correct 421 ms 75404 KB Output is partially correct - L = 720371712
26 Partially correct 436 ms 75300 KB Output is partially correct - L = 720109568
27 Partially correct 446 ms 75436 KB Output is partially correct - L = 719847424