Submission #1059389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059389		Piokemon	City (JOI17_city)	C++17	96 / 100	200 ms	42780 KiB

Encoder

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

constexpr int N = 25e4;
vector<int> graf[N+9];
ll pre[N+9];
ll post[N+9];
int skok[N+9];
vector<pair<ll,int>> skoki;
ll tajm=1;
int n;

void dfs(int v, int par){
	pre[v]=tajm++;
	for (int x:graf[v]){
		if (x!=par)dfs(x,v);
	}
	ll rozn=tajm-pre[v];
	auto it = upper_bound(skoki.begin(),skoki.end(),make_pair(rozn,0));
	tajm=pre[v]+(*it).first;
	skok[v]=(*it).second;
	post[v]=tajm;
}

void Encode(int n_, int A[], int B[]){
	skoki.push_back({1,0});
	for (int x=1;x<300;x++){
		double duppa = (double) (skoki.back().first) * (double)1.05;
		skoki.push_back({ceil(duppa),x});
	}
	skoki.push_back({1e9,1e9});
	n=n_;
	for (int i = 1; i < n; ++i) {
		graf[A[i-1]].push_back(B[i-1]);
		graf[B[i-1]].push_back(A[i-1]);
	}
	dfs(0,-1);
	for (ll x=0;x<n;x++){
		//cerr << pre[x] << ' ' << post[x] << '\n';
		Code(x,skoki.size()*pre[x]+skok[x]);
	}
}

Device

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

vector<pair<ll,int>> skoki2;

void InitDevice(){
	skoki2.push_back({1,0});
	for (int x=1;x<300;x++){
		double duppa = (double) (skoki2.back().first) * (double)1.05;
		skoki2.push_back({ceil(duppa),x});
	}
	skoki2.push_back({1e9,1e9});
}


int Answer(long long S, long long T){
	
	ll ps,ks,pt,kt;
	ps = S/skoki2.size();
	ks=ps+skoki2[S%skoki2.size()].first;
	pt = T/skoki2.size();
	kt=pt+skoki2[T%skoki2.size()].first;
	if (ps<=pt && kt<=ks)return 1;
	if (pt<=ps && ks<=kt)return 0;
	return 2;
}

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