Submission #114250

#	Time	Username	Problem	Language	Result	Execution time	Memory
114250		faustaadp	City (JOI17_city)	C++17	22 / 100	703 ms	116248 KiB

Encoder

#include "Encoder.h"

#include <vector>
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll x[552525],ki[552525],ka[552525],sz,dep[552525],te;
vector<ll> v[552525];

void dfs(ll aa,ll bb)
{
	ll ii,sz=0;
	vector<ll> tem;
	priority_queue<pair<ll,ll> > pq;
	for(ii=0;ii<(ll)v[aa].size();ii++)
		if(v[aa][ii]!=bb)
		{
			dfs(v[aa][ii],aa);
			sz++;
			pq.push(mp(-dep[v[aa][ii]],v[aa][ii]));
		}
	while(sz>2)
	{
		ll xa=pq.top().se;
		pq.pop();
		ll xb=pq.top().se;
		pq.pop();
		te++;
		dep[te]=max(dep[xa],dep[xb])+1;
		ki[te]=xa;
		ka[te]=xb;
		pq.push(mp(-dep[te],te));
		sz--;
	}
	if(sz==2)
	{
		ll xa=pq.top().se;
		pq.pop();
		ll xb=pq.top().se;
		pq.pop();
		dep[aa]=max(dep[xa],dep[xb])+1;
		ki[aa]=xa;
		ka[aa]=xb;	
	}
	else
	if(sz==1)
	{
		ll xa=pq.top().se;
		pq.pop();
		dep[aa]=dep[xa]+1;
		ki[aa]=xa;
	}
	else
		dep[aa]=1;
}
void dfs2(ll aa,ll cc)
{
	if(aa==-1)return;
	x[aa]=cc;
	dfs2(ki[aa],cc*2+1);	
	dfs2(ka[aa],cc*2+2);	
}
void Encode(int N, int A[], int B[])
{
	int i;
 	for(i=0;i<(N-1);i++)
 	{
 		v[A[i]].pb(B[i]);
 		v[B[i]].pb(A[i]);
 	} 
 	te=N;
 	memset(ki,-1,sizeof(ki));
 	memset(ka,-1,sizeof(ka));
 	dfs(0,0);
 	dfs2(0,0);
 	for(i=0;i<N;i++)
 	{
 	//	cout<<i<<"->"<<x[i]<<"\n";
 		Code(i, x[i]);
 	}
}

Device

#include "Device.h"

void InitDevice() {

}

int Answer(long long S, long long T) {
	if(S<T)
	{
		while(T>S)
		{
			T--;
			T/=2;	
		}
		if(T==S)return 1;
		return 2;
	}
	else
	{
		while(S>T)
		{
			S--;
			S/=2;
		}
		if(S==T)return 0;
  		return 2;
	}
}

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