Submission #413737

#	Time	Username	Problem	Language	Result	Execution time	Memory
413737		alishahali1382	City (JOI17_city)	C++14	100 / 100	583 ms	42828 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002;

int n, m, k, u, v, SZ;
int stt[MAXN], fnt[MAXN], timer;
int par[MAXN], h[MAXN], sz[MAXN];
int shit[MAXN];
vector<int> G[MAXN];

int dfs1(int node){
	if (node){
		for (int &v:G[node]) if (v==par[node]) swap(v, G[node].back());
		G[node].pop_back();
	}
	sz[node]=1;
	for (int v:G[node]){
		par[v]=node;
		h[v]=h[node]+1;
		sz[node]+=dfs1(v);
	}
	return sz[node];
}
void dfs2(int node){
	stt[node]=timer++;
	sort(all(G[node]), [](int i, int j){
		return sz[i]>sz[j];
	});
	for (int v:G[node]) dfs2(v);
	fnt[node]=timer;
}

void Encode(int _n, int A[], int B[]){
	for (int i=0; i<800; i++) shit[SZ++]=i+1;
	ld eps=.05, val=shit[SZ-1];
	while (shit[SZ-1]<MAXN){
		val+=val*eps;
		// val+=log2(log2(val))*20;
		int x=val;
		if (x>MAXN) x=MAXN;
		if (x!=shit[SZ-1]) shit[SZ++]=x;
	}
	SZ=unique(shit, shit+SZ)-shit;
	debug(SZ)
	// fuck
	
	n=_n;
	for (int i=0; i<n-1; i++){
		u=A[i];
		v=B[i];
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs1(0);
	dfs2(0);

	for (int i=0; i<n; i++){
		int szz=lower_bound(shit, shit+SZ, sz[i])-shit;
		Code(i, 1ll*szz*MAXN + stt[i]);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002, LOG=60;

int Shit[MAXN], SZZ;

void InitDevice(){
	for (int i=0; i<800; i++) Shit[SZZ++]=i+1;
	ld eps=.05, val=Shit[SZZ-1];
	while (Shit[SZZ-1]<MAXN){
		val+=val*eps;
		// val+=log2(log2(val))*20;
		int x=val;
		if (x>MAXN) x=MAXN;
		if (x!=Shit[SZZ-1]) Shit[SZZ++]=x;
	}
	SZZ=unique(Shit, Shit+SZZ)-Shit;
	debug(SZZ)
	// fuck
}

int Answer(ll S, ll T){
	int szx=Shit[S/MAXN], sttx=S%MAXN, fntx=sttx+szx;
	int szy=Shit[T/MAXN], stty=T%MAXN, fnty=stty+szy;
	// debug2(sttx, fntx)
	// debug2(stty, fnty)
	if (stty<=sttx && sttx<fnty) return 0;
	if (sttx<=stty && stty<fntx) return 1;
	return 2;
}

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