Submission #427385

#	Time	Username	Problem	Language	Result	Execution time	Memory
427385		kai824	City (JOI17_city)	C++17	8 / 100	269 ms	48604 KiB

Encoder

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

vector<int> adjl[250005];
ll pre[250005],sub[250005],nex;

ll cnts[250005];
void init(){
	for(int i=1;i<250000;i++){
		cnts[i]=cnts[i-1]+(250000-i);
	}
}

ll convert(int x,int y){//returns no. of smaller pairs...
	y-=x;
	assert(cnts[x]+y<cnts[x+1]);
	return cnts[x]+y;
}

void dfs(int node,int p=-1){
	pre[node]=nex++;
	for(int x:adjl[node]){
		if(x==p)continue;
		dfs(x,node);
	}
	sub[node]=nex-1;
	// cout<<node<<' '<<pre[node]<<' '<<sub[node]<<'\n';
	Code(node,convert(pre[node],sub[node]));
}

void Encode(int n, int a[], int b[]){
	init();
	for(int i=0;i+1<n;i++){
		adjl[a[i]].push_back(b[i]);
		adjl[b[i]].push_back(a[i]);
	}
	dfs(0);
	//Code(i, 0LL): node, label...
}

Device

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

ll cnt[250005];
void InitDevice(){
	cnt[0]=0;
	for(int i=1;i<250000;i++){
		cnt[i]=cnt[i-1]+(250000-i);
	}
}
void unpack(ll x,int&a, int&b){
	// for(int i=0;i<250000;i++){
	// 	if(x>=cnt[i]){
	// 		a=i;
	// 		b=x-cnt[i];
	// 	}
	// }
	a=upper_bound(cnt,cnt+250000,x)-cnt-1;
	b=x-cnt[a]+a;
	//cout<<x<<' '<<a<<' '<<b<<'\n';
}

int Answer(long long s, long long t){
	int p1,p2,s1,s2;
	unpack(s,p1,s1);
	unpack(t,p2,s2);
	if(p1<p2 && p2<=s1)return 1;
	if(p2<p1 && p1<=s2)return 0;
	return 2;
}

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