Submission #1066121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066121		Unforgettablepl	City (JOI17_city)	C++17	30 / 100	328 ms	47068 KiB

Encoder

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

const int MaxN = 250000;

namespace {
	long long combiner(long long l,long long r) {
		return ((r+1ll)*(r))/2ll + l;
	}
}

void Encode(int N, int A[], int B[]){
	vector<vector<int>> adj(N);
	for(int i=0;i<N-1;i++) {
		adj[A[i]].emplace_back(B[i]);
		adj[B[i]].emplace_back(A[i]);
	}
	int tim = -1;
	vector<int> starts(N);
	vector<int> ends(N);
	function<void(int,int)> dfs = [&](int x,int p) {
		int start =++tim;
		for(int&i:adj[x])if(i!=p) {
			dfs(i,x);
		}
		Code(x,combiner(start,tim));
	};
	dfs(0,-1);
}

Device

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

const int MaxN = 250000;

namespace {
	vector<long long> ranges;
	void init_ranges() {
		for(long long r=0;r<MaxN;r++) {
			ranges.emplace_back(((r+1ll)*r)/2ll);
		}
	}
	pair<int,int> decombiner(long long x){
		auto iter = upper_bound(ranges.begin(),ranges.end(),x);iter--;
		x-=*iter;
		return {x,iter-ranges.begin()};
	}
}

void InitDevice(){
	init_ranges();
}

int Answer(long long S, long long T){
	auto [l1,r1] = decombiner(S);
	auto [l2,r2] = decombiner(T);
	if(l1<=l2 and r2<=r1)return 1;
	if(l2<=l1 and r1<=r2)return 0;
	return 2;
}

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