Submission #134158

#	Time	Username	Problem	Language	Result	Execution time	Memory
134158		AngusRitossa	City (JOI17_city)	C++14	8 / 100	3031 ms	169840 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#ifdef DEBUG
	#define D(x...) printf(x)
#else	
	#define D(x...)
#endif
using namespace std;
typedef long long ll;
static vector<int> adj[250010];
static int seen[250010];
static int sz[250010];
set<ll> visited;
int findsz(int a)
{
	if (sz[a]) return sz[a];
	sz[a] = 1;
	for (auto b : adj[a])
	{
		if (sz[b]) continue;
		sz[a] += findsz(b);
	}
	return sz[a];
}
void dfs(int a, ll node);
void dothing(int a, ll node, vector<pair<int, int> >& children)
{
	visited.insert(node);
	if (children.empty()) return;
	int sum = accumulate(children.begin(), children.end(), 0, [](const int &a, const pair<int, int> &b) { return a+b.first;});
	int am = 0;
	vector<pair<int, int> > after;
	for (int i = children.size()-1; i >= 0; i--)
	{
		after.push_back(children[i]);
		am += children[i].first;
	//	D("%d: here %d, %d, sum %d\n", a, am, i, sum);
		children.pop_back();
		if (am >= sum/2)
		{
			reverse(after.begin(), after.end());
			assert(children.size());
			if (children.size() == 1)
			{
				dfs(children[0].second, 2*node);
			}
			else dothing(a, 2*node, children);
			if (after.size() == 1) dfs(after[0].second, 2*node+1);
			else dothing(a, 2*node+1, after);
			return;
		}
	}
}

void dfs(int a, ll node)
{
	visited.insert(node);
	vector<pair<int, int> > children;
	seen[a] = 1;
	Code(a, node);
	D("%d: %lld\n", a, node);
	for (auto b : adj[a])
	{
		if (seen[b]) continue;
		children.push_back({sz[b], b});
	}
	sort(children.begin(), children.end());
	if (children.size() == 1) dfs(children[0].second, 2*node);
	else dothing(a, node, children);
}
map<ll, int> mxstorage;
int mxdepth(ll a)
{
	if (visited.find(a) == visited.end()) return 0;
	if (mxstorage.find(a) != mxstorage.end()) return mxstorage[a];
	return mxstorage[a] = max(mxdepth(2*a), mxdepth(2*a+1))+1;
}
void dfs2(ll a, int depth, int alloweddepth)
{
	if (visited.find(a) == visited.end()) return;
	assert(depth+mxdepth(a) <= alloweddepth);
	dfs2(2*a, depth+1, alloweddepth);
	dfs2(2*a, depth+1, alloweddepth);
}
void Encode(int n, int a[], int b[])
{
	for (int i = 0; i < n-1; i++)
	{
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	findsz(0);
	dfs(0, 1);
	dfs2(1, 0, 36);
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void InitDevice()
{

}
ll LOG2(ll a)
{
	int ans = 0;
	while (a)
	{
		ans++;
		a/=2;
	}
	return ans;
}
int Answer(ll s, ll t)
{
	int hei1 = LOG2(s);
	int hei2 = LOG2(t);
	int sbigger = hei1 < hei2;
	while (hei1 > hei2) hei1--, s/=2;
	while (hei1 < hei2) hei2--, t/=2;
	if (s == t) return sbigger;
	else return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92