Submission #218099

#	Time	Username	Problem	Language	Result	Execution time	Memory
218099		patrikpavic2	City (JOI17_city)	C++17	22 / 100	696 ms	118848 KiB

Encoder

#include "Encoder.h"
#include <vector>
#include <cstdio>
#include <set>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;

const int N = 5e5 + 500;

vector < int > v[N];
int d0[N], d1[N], sub[N], dulj[N], nww = 0, n;
ll tko[N];
set < pii > S;

void dfs_triv(int x,int lst){
	sub[x] = 1;
	for(int y : v[x]){
		if(y != lst){
			dfs_triv(y, x); 
			sub[x] += sub[y];
		}
	}
}

void glupi(int x, int duljina){
	if(x < 0) return;
	if(x < n){
	//	printf("x = %d tko = %lld dulj = %d\n", x, tko[x] + (1 << duljina), duljina);
		Code(x, tko[x] + (1LL << duljina));
	}
	if(d0[x] >= 0)
		tko[d0[x]] = tko[x];
	if(d1[x] >= 0)
		tko[d1[x]] = tko[x] + (1LL << duljina); 
	glupi(d0[x], duljina + 1); glupi(d1[x], duljina + 1);
}


void dfs(int x, int lst){
	for(int y : v[x]){
		if(y == lst) continue;
		dfs(y, x);
	}
	for(int y : v[x])
		if(y != lst)
			S.insert({dulj[y], y});
	d0[x] = -1, d1[x] = -1;
	if((int)S.size() >= 2){
		for(;S.size() > 1;){
			int nw = nww++;
			if((int)S.size() == 2) 
				nw = x, nww--;
			d0[nw] = S.begin() -> Y; S.erase(S.begin()); 
			d1[nw] = S.begin() -> Y; S.erase(S.begin()); 
			dulj[nw] = max(dulj[d0[nw]], dulj[d1[nw]]) + 1; 
			//printf("nw = %d\n", nw);
			S.insert({dulj[nw], nw}); 
		}
	}
	else{
		for(int y : v[x]){
			if(y == lst) continue;
			d0[x] = y; 
			dulj[x] = dulj[y] + 1;
		}
	}
	S.clear();
}

void Encode(int nn, int u1[], int u2[]){
	n = nn;
	for(int i = 0;i + 1 < n;i++)
		v[u1[i]].PB(u2[i]),
		v[u2[i]].PB(u1[i]);
	nww = n;
	dfs_triv(0, 0);
	dfs(0, 0);
	glupi(0, 0);
}

Device

#include "Device.h"
#include <cstdio>

typedef long long ll;

void InitDevice(){
	return;
}

bool dijete(ll A, ll B){
	int dulj_A = 0, dulj_B = 0;
	for(;(1LL << dulj_A) <= A;dulj_A++);
	for(;(1LL << dulj_B) <= B;dulj_B++);
	if(dulj_A >= dulj_B) return 0;
	//printf("dulj_A = %d dulj_B = %d\n", dulj_A, dulj_B);
	//printf("Je li B %lld dijete od A %lld\n", B, A);
	for(int i = 0;i + 1 < dulj_A;i++){
		if((A & (1LL << i)) != (B & (1LL << i)))
			return 0;
	}
	//printf("DA\n");
	return 1;
}

int Answer(ll A, ll B)
{
	if(dijete(B, A)) 
		return 0;
	if(dijete(A, B)) 
		return 1;
	return 2;
}

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