Submission #1257594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257594		makrav	City (JOI17_city)	C++20	18 / 100	397 ms	32264 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

void Encode(int N, int A[], int B[])
{
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; i++) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	vector<int> sub(N);
	vector<vector<int>> g2(N);
	auto dfs = [&](int v, int p, auto&&self) -> void {
		sub[v] = 1;
		for (int u : g[v]) {
			if (u != p) {
				g2[v].pb(u);
				self(u, v, self);
				sub[v] += sub[u];
			}
		}
	};
	dfs(0, 0, dfs);
	auto sol = [&](vector<int> roots, int h, ll code, auto&&self) -> void {
		// ?for (int u : roots) cout << u << ' ';
		// cout << h << ' ' << code << '\n';
		if (roots.empty()) return;
		vector<int> r2;
		if (roots.size() == 1) {
			//cout << "enc " << roots[0] << ' ' << (1ll << h) + code << '\n';
			Code(roots[0], (1ll << h) + code);
			for (int u : g2[roots[0]]) {
				r2.pb(u);
			}
		} else {
			r2 = roots;
		}
		if (r2.empty()) return;
		sort(all(r2), [&](int x, int y) {
			return sub[x] > sub[y];
		});
		int ts = 0, cts = 0;
		for (int u : r2) ts += sub[u];
		for (int j = 0; j < sz(r2); j++) {
			cts += sub[r2[j]];
			if (cts >= ts / 2) {
				vector<int> fr, sc;
				if (j > 0) j--;
				for (int jj = 0; jj <= j; jj++) fr.pb(r2[jj]);
				for (int jj = j + 1; jj < sz(r2); jj++) sc.pb(r2[jj]);
				self(fr, h + 1, code, self);
				self(sc, h + 1, code + (1ll << h), self);
				break;
			}
		}
	};
	sol({0}, 0, 0, sol);
}		

Device

#include "Device.h"
#include <cassert>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void InitDevice()
{
}

int Answer(long long S, long long T)
{
	assert(S != T);
	ll H1 = 63 - __builtin_clzll(S), H2 = 63 - __builtin_clzll(T);
	S -= (1ll << H1); T -= (1ll << H2);
	//cout << H1 << ' ' << H2 << ' ' << S << ' ' << T << '\n';
	if (H1 == H2) return 2;
	if (H1 < H2) {
		if ((T % (1ll << H1)) == S) return 1;
		return 2;
	} else {
		if ((S % (1ll << H2)) == T) return 0;
		return 2;
	}
	// if ((S&T) != std::min(S, T)) return 2;
	// if (H1 < H2) return 1;
	// return 0;
}

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