oj.uz

Submission #564345

# Submission time Handle Problem Language Result Execution time Memory
564345 2022-05-19T03:17:49 Z blue City (JOI17_city) C++17
74 / 100
 433 ms 83028 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;
const int abits = 20;
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] << 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 mx = 800'000;
	const int abits = 20;
 
	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>>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 21 ms 44780 KB Output is correct
2 Correct 22 ms 44676 KB Output is correct
3 Correct 22 ms 44644 KB Output is correct
4 Correct 21 ms 44760 KB Output is correct
5 Correct 21 ms 44756 KB Output is correct
6 Correct 21 ms 44776 KB Output is correct
7 Correct 22 ms 44704 KB Output is correct
8 Correct 22 ms 44536 KB Output is correct
9 Correct 23 ms 44828 KB Output is correct
10 Correct 23 ms 45020 KB Output is correct
11 Correct 23 ms 44668 KB Output is correct
12 Correct 20 ms 44748 KB Output is correct

Subtask #2
66.0 / 92.0

# Verdict Execution time Memory Grader output
1 Partially correct 176 ms 59516 KB Output is partially correct - L = 504365056
2 Partially correct 183 ms 59436 KB Output is partially correct - L = 504365056
3 Partially correct 174 ms 59528 KB Output is partially correct - L = 503316480
4 Partially correct 175 ms 59488 KB Output is partially correct - L = 503316480
5 Partially correct 419 ms 81688 KB Output is partially correct - L = 1559232512
6 Partially correct 425 ms 82236 KB Output is partially correct - L = 1559232512
7 Partially correct 417 ms 82284 KB Output is partially correct - L = 1559232512
8 Partially correct 433 ms 81928 KB Output is partially correct - L = 1561329664
9 Partially correct 363 ms 82924 KB Output is partially correct - L = 1568669696
10 Partially correct 349 ms 82768 KB Output is partially correct - L = 1572864000
11 Partially correct 341 ms 83028 KB Output is partially correct - L = 1573912576
12 Partially correct 346 ms 82900 KB Output is partially correct - L = 1573912576
13 Partially correct 392 ms 82528 KB Output is partially correct - L = 1564475392
14 Partially correct 402 ms 82256 KB Output is partially correct - L = 1562378240
15 Partially correct 182 ms 60152 KB Output is partially correct - L = 504365056
16 Partially correct 185 ms 60080 KB Output is partially correct - L = 504365056
17 Partially correct 179 ms 60040 KB Output is partially correct - L = 504365056
18 Partially correct 401 ms 82380 KB Output is partially correct - L = 1572864000
19 Partially correct 409 ms 82316 KB Output is partially correct - L = 1572864000
20 Partially correct 404 ms 82728 KB Output is partially correct - L = 1572864000
21 Partially correct 419 ms 82620 KB Output is partially correct - L = 1567621120
22 Partially correct 425 ms 82440 KB Output is partially correct - L = 1572864000
23 Partially correct 408 ms 82724 KB Output is partially correct - L = 1572864000
24 Partially correct 424 ms 82528 KB Output is partially correct - L = 1571815424
25 Partially correct 425 ms 82436 KB Output is partially correct - L = 1570766848
26 Partially correct 419 ms 82364 KB Output is partially correct - L = 1569718272
27 Partially correct 426 ms 82620 KB Output is partially correct - L = 1567621120