Submission #122732

#	Time	Username	Problem	Language	Result	Execution time	Memory
122732		ainta	City (JOI17_city)	C++17	8 / 100	210 ms	61936 KiB

Encoder

#include "Encoder.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<array>
#define N_ 501000
using namespace std;
int TH = 127;
vector<int>E[N_], Ch[N_];
int C[N_], cnt, n, par[N_];

void DFS(int a, int pp) {
	C[a] = 1;
	par[a] = pp;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);
		Ch[a].push_back(x);
		C[a] += C[x];
	}
}

int Num[N_], Num2[N_], Ed[N_], cc, PP[N_], Ed2[N_];

void DFS2(int a) {
	Num[a] = ++cc;
	for (auto &x : Ch[a]) {
		DFS2(x);
	}
	Ed[a] = cc;
}

void DFS3(int a) {
	Num[a] = ++cc;
	if (a >= n)return;
	for (auto &x : Ch[a]) {
		DFS3(x);
	}
	Ed[a] = cc;
}
void DFS4(int a, int pp) {
	PP[a] = pp;
	Num2[a] = ++cc;
	for (auto &x : Ch[a]) {
		DFS4(x, pp);
	}
	Ed2[a] = cc;
}

void Encode(int N, int A[], int B[])
{
	for (int i = 0; i < N - 1; ++i) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(0, -1);
	cnt = N - 1;
	int i, j;
	n = N;
	for (i = 0; i < N; i++) {
		if (C[i] >= TH) {
			int ck = 0, sss = 0;
			for (auto &x : Ch[i]) {
				if (C[x] >= TH)sss = 1;
			}
			if (sss == 1)continue;
			Ch[i].clear();
			vector<int>T;
			int s = 0;
			for (auto &x : Ch[i]) {
				if (s + C[x] >= TH) {
					++cnt;
					Ch[i].push_back(cnt);
					for (auto &y : T)Ch[cnt].push_back(y);
					s = 0;
					T.clear();
				}
				T.push_back(x);
				s += C[x];
			}
			++cnt;
			Ch[i].push_back(cnt);
			for (auto &y : T)Ch[cnt].push_back(y);
			s = 0;
			T.clear();
		}
	}
	if (cnt == N - 1) {
		DFS2(0);
		if (cc >= (1 << 14)) {
			while (1) {}
		}
	}
	else {
		cc = 0;
		DFS3(0);
		if (cc >= (1 << 13)) {
			while (1) {}
		}
		for (i = N; i <= cnt; i++) {
			cc = 0;
			DFS4(i, i);
			if (cc >= TH + 1) {
				while (1) {}
			}
		}
	}
	for (i = 0; i < N; i++) {
		int r = 0;
		if (PP[i]) {
			r += (1 << 27);
			r += (Num[PP[i]] << 14);
			r += (Num2[i] << 7);
			r += Ed2[i];
		}
		else {
			r += (Num[i] << 13);
			r += Ed[i];
		}
		Code(i, r);
	}
}

Device

#include "Device.h"
 
void InitDevice()
{
}
 
int Answer(long long S, long long T)
{
	int ck1 = (S >> 27), ck2 = (T >> 27);
	S &= ((1 << 27) - 1);
	T &= ((1 << 27) - 1);
 
	if (ck1 == 0 && ck2 == 0) {
		int bS = (S >> 13), eS = S & ((1 << 13) - 1);
		int bT = (T >> 13), eT = T & ((1 << 13) - 1);
		if (bS <= bT && eT <= eS)return 1;
		if (bT <= bS && eS <= eT)return 0;
		return 2;
	}
	else if (ck1 == 0 && ck2 == 1) {
		int bS = (S >> 13), eS = S & ((1 << 13) - 1);
		int TT = (T >> 14);
		if (bS <= TT && TT <= eS)return 1;
		return 2;
	}
	else if (ck1 == 1 && ck2 == 0) {
		int bS = (T >> 13), eS = T & ((1 << 13) - 1);
		int TT = (S >> 14);
		if (bS <= TT && TT <= eS)return 0;
		return 2;
	}
	else {
		if ((S >> 14) != (T >> 14))return 2;
		int ss = (S&((1 << 14) - 1));
		int tt = (T&((1 << 14) - 1));
		int bS = (ss >> 7), eS = (ss & 127);
		int bT = (tt >> 7), eT = (tt & 127);
		if (bS <= bT && eT <= eS)return 1;
		if (bT <= bS && eS <= eT)return 0;
		return 2;
	}
}

Compilation message (stderr)

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:63:8: warning: unused variable 'ck' [-Wunused-variable]
    int ck = 0, sss = 0;
        ^~
Encoder.cpp:59:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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