Submission #427415

#	Time	Username	Problem	Language	Result	Execution time	Memory
427415		oolimry	City (JOI17_city)	C++17	0 / 100	341 ms	21000 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

vector<int> adj[250005];
vector<int> seq[250005];
int worst[250005];

int target = 36;

vector<int> conv(int val, int L){
	vector<int> V;
	while(L--){
		V.push_back(val&1);
		val /= 2;
	}
	reverse(all(V));
	return V;
}

void dfs(int u, int p){
	vector<ii> stuff;
	for(int v : adj[u]){
		if(v == p) continue;
		dfs(v, u);
		stuff.push_back(ii(worst[v], v));
	}
	
	int low = 0, high = 70;
	while(low != high-1){
		int mid = (low+high)/2;
		int total = 0;
		
		for(ii x : stuff){
			total += (1<<x.first);
		}
		
		if(total <= (1<<mid)) high = mid;
		else low = mid;
	}
	
	sort(all(stuff));
	
	int val = 0;
	int h = high;
	int has = 0;
	for(ii x : stuff){
		int L = high-x.first;
		
		while(h > L){
			val >>= 1;
			h--;
		}
		
		if(has) val++;
		else has = 1;
		
		//show3(x.second, val, L);
		seq[x.second] = conv(val, L);
	}
	
	worst[u] = high;
	//show2(u, worst[u]);
}

vector<int> V;

lint conv2(){
	int L = sz(V);
	lint val = 0;
	for(int x : V){
		val *= 2;
		val += x;
	}
	val *= target;
	val += L;
	return val;
}

void dfs2(int u, int p){
	for(int x : seq[u]) V.push_back(x);
	Code(u, conv2());
	
	//show(u);
	//for(int x : V) cerr << x << " "; cerr << endl;
	
	for(int v : adj[u]){
		if(v == p) continue;
		dfs2(v, u);
	}
	for(int x : seq[u]) V.pop_back();
}

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]);
	}
	
	dfs(0, -1);
	
	for(int i = 1;i < n;i++){
		//for(int x : seq[i]) cerr << x << " ";
		//cerr << '\n';
	}
	
	dfs2(0, -1);
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

int target2 = 36;
void InitDevice(){
	
}

vector<int> conv(lint A){
	lint L = A % target2;
	A /= target2;
	
	vector<int> v;
	for(int i = 0;i < L;i++){
		v.push_back(A&1);
		A /= 2;
	}
	reverse(all(v));
	return v;
}

int Answer(long long S, long long T){
	auto s = conv(S);
	auto t = conv(T);
	
	for(int i = 0;i < min(sz(s), sz(t));i++){
		if(s[i] != t[i]) return 2;
	}
	
	if(sz(s) < sz(t)) return 1;
	else return 0;
}

Compilation message (stderr)

Encoder.cpp: In function 'void dfs2(int, int)':
Encoder.cpp:99:10: warning: unused variable 'x' [-Wunused-variable]
   99 |  for(int x : seq[u]) V.pop_back();
      |          ^

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