Submission #71934

#	Time	Username	Problem	Language	Result	Execution time	Memory
71934		IvanC	City (JOI17_city)	C++17	22 / 100	618 ms	82240 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250010;

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

static vector<ii> guloso[MAXN];
static vector<int> grafo[MAXN];
static int tam[MAXN],ini[MAXN],fim[MAXN],dfsCount;

static void dfs_sz(int v,int p){

	tam[v] = 1;
	int tem_folha = 0;

	for(int u : grafo[v]){
		if(u == p) continue;
		dfs_sz(u,v);
		if(tam[u] != 1){
			tam[v] += tam[u];
		}
		else{
			if(!tem_folha){
				tem_folha = 1;
				tam[v] += 1;
			}
		}
	}

}

static void dfs_euler(int v,int p){

	ini[v] = ++dfsCount;

	int tem_folha = 0;

	for(int u : grafo[v]){
		if(u == p) continue;
		guloso[v].push_back(ii(tam[u],u));
	}

	sort(guloso[v].rbegin(),guloso[v].rend());

	for(ii par : guloso[v]){

		int sz_u = par.first, u = par.second;

		if(sz_u != 1){
			dfs_euler(u,v);
		}
		else{
			if(!tem_folha){
				tem_folha++;
				dfsCount++;
				ini[u] = dfsCount;
				fim[u] = dfsCount;
			}
			else{
				ini[u] = dfsCount;
				fim[u] = dfsCount;
			}
		}

	}

	fim[v] = dfsCount;

}

static long long coding1(int A,int B){

	B -= A;

	long long davez = A;
	davez += (1LL << 18)*ll(B);

	return (davez << 1);

}

static long long coding2(int A,int B){

	B -= A;

	swap(A,B);

	long long davez = A;
	davez += (1LL << 18)*ll(B);

	return (davez << 1) | 1;

}

void Encode(int N, int A[], int B[]){

	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}

	dfs_sz(0,-1);
	dfs_euler(0,-1);

	for(int i = 0;i<N;i++){
		ini[i]--;
		fim[i]--;
	}

	for (int i = 0; i < N; ++i) {
		Code(i, min(coding1(ini[i],fim[i]), coding2(ini[i],fim[i]) ) );
	}

}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

void InitDevice(){
	
}

static void Magic(long long X, int &ini, int& fim ){

	ini = 0;
	fim = 0;

	long long flag = (X & 1);
	X >>= 1;

	long long temp = (X >> 18);
	fim += temp;

	X -= (temp)*(1 << 18);

	ini += X;

	if(flag) swap(ini,fim);

	fim += ini;

}

int Answer(long long S, long long T){

	if(S == T) return 2;

	int inia,fima,inib,fimb;

	Magic(S,inia,fima);
	Magic(T,inib,fimb);

	if(inia <= inib && inib <= fima) return 1;
	if(inib <= inia && inia <= fimb) return 0;

	return 2;

}

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