Submission #1057485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057485		Piokemon	City (JOI17_city)	C++17	8 / 100	181 ms	55352 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];
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];
	ll temp=1;
	while(temp<rozn)temp*=2;
	tajm=pre[v]+temp;
	post[v]=tajm;
}

void Encode(int n_, int A[], int B[]){
	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);
	ll stala=60;
	for (ll x=0;x<n;x++){
		//cerr << pre[x] << ' ' << post[x] << '\n';
		Code(x,stala*pre[x]+__lg(post[x]-pre[x]));
	}
}

Device

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

constexpr ll stala = 60;

void InitDevice(){
	//uwu
}

int Answer(long long S, long long T){
	ll pres,is,pret,it;
	pres=S/stala; is=S%stala;
	pret=T/stala; it=T%stala;
	ll posts,postt;
	posts=pres+(1LL<<is);
	postt=pret+(1LL<<it);
	if (pres<=pret && postt<=posts)return 1;
	if (pret<=pres && posts<=postt)return 0;
	return 2;
}

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