oj.uz

Submission #564245

# Submission time Handle Problem Language Result Execution time Memory
564245 2022-05-18T19:36:40 Z blue City (JOI17_city) C++17
46 / 100
 574 ms 74560 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.0001;
	set<ll> res;
	res.insert(1);
 
	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, 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 = 700'000;
 
	vll getsizes()
	{
		double base = 1.0001;
		set<ll> res;
		res.insert(1);
 
		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)
{
	// 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 44 ms 45312 KB Output is correct
2 Correct 42 ms 45116 KB Output is correct
3 Correct 49 ms 45208 KB Output is correct
4 Correct 48 ms 45216 KB Output is correct
5 Correct 45 ms 45272 KB Output is correct
6 Correct 44 ms 45224 KB Output is correct
7 Correct 46 ms 45228 KB Output is correct
8 Correct 48 ms 45352 KB Output is correct
9 Correct 48 ms 45244 KB Output is correct
10 Correct 51 ms 45324 KB Output is correct
11 Correct 41 ms 45344 KB Output is correct
12 Correct 41 ms 45384 KB Output is correct

Subtask #2
38.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 53528 KB Output is correct - L = 183238656
2 Correct 188 ms 53492 KB Output is correct - L = 182976512
3 Correct 215 ms 53516 KB Output is correct - L = 183238656
4 Correct 201 ms 53396 KB Output is correct - L = 183238656
5 Partially correct 459 ms 73176 KB Output is partially correct - L = 11059855360
6 Partially correct 484 ms 73148 KB Output is partially correct - L = 11059855360
7 Partially correct 517 ms 73208 KB Output is partially correct - L = 11059855360
8 Partially correct 481 ms 72828 KB Output is partially correct - L = 11059593216
9 Partially correct 412 ms 73788 KB Output is partially correct - L = 11061952512
10 Partially correct 354 ms 73760 KB Output is partially correct - L = 11061428224
11 Partially correct 387 ms 73828 KB Output is partially correct - L = 11062214656
12 Partially correct 416 ms 74560 KB Output is partially correct - L = 11063525376
13 Partially correct 461 ms 73848 KB Output is partially correct - L = 11061166080
14 Partially correct 444 ms 73224 KB Output is partially correct - L = 11060379648
15 Correct 202 ms 53556 KB Output is correct - L = 183238656
16 Correct 195 ms 53472 KB Output is correct - L = 183238656
17 Correct 200 ms 53468 KB Output is correct - L = 183238656
18 Partially correct 431 ms 73268 KB Output is partially correct - L = 11063001088
19 Partially correct 418 ms 73288 KB Output is partially correct - L = 11063525376
20 Partially correct 489 ms 73324 KB Output is partially correct - L = 11063525376
21 Partially correct 504 ms 73224 KB Output is partially correct - L = 11061690368
22 Partially correct 508 ms 73256 KB Output is partially correct - L = 11063263232
23 Partially correct 571 ms 73216 KB Output is partially correct - L = 11063525376
24 Partially correct 499 ms 73132 KB Output is partially correct - L = 11063263232
25 Partially correct 510 ms 73080 KB Output is partially correct - L = 11063001088
26 Partially correct 574 ms 73012 KB Output is partially correct - L = 11062738944
27 Partially correct 535 ms 72956 KB Output is partially correct - L = 11062214656