oj.uz

Submission #427862

# Submission time Handle Problem Language Result Execution time Memory
427862 2021-06-15T02:38:12 Z jamezzz City (JOI17_city) C++17
100 / 100
 581 ms 53712 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

#define maxn 250005
int pre[maxn],pst[maxn],cnt;
vector<int> seq,AL[maxn];

void build(){
	const long double factor = 1.055645;
	seq.pb(0);seq.pb(1);
	for(int i=2;i<256;++i){
		int x=(int)(factor*seq.back());
		if(x==seq.back())++x;
		seq.pb(x);
	}
}

void dfs(int u){
	pre[u]=cnt++;
	for(int v:AL[u]){
		if(pre[v]==-1)dfs(v);
	}
	int pos=lower_bound(all(seq),cnt-pre[u])-seq.begin();
	cnt+=seq[pos]+pre[u]-cnt;
	pst[u]=cnt-1;
}

void Encode(int n,int a[],int b[]){
	build();
	memset(pre,-1,sizeof pre);
	for(int i=0;i<n-1;++i){
		AL[a[i]].pb(b[i]);
		AL[b[i]].pb(a[i]);
	}
	dfs(0);
	//for(int i=0;i<n;++i)pf("%d %d\n",pre[i],pst[i]);
	for(int i=0;i<n;++i){
		int dist=pst[i]-pre[i]+1;
		int x=lower_bound(all(seq),dist)-seq.begin();
		assert(x<sz(seq)&&seq[x]==dist);
		Code(i,(1ll<<20)*x+pre[i]);
	}
}

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

int ones=(1<<20)-1;

vector<int> seq2;

void build2(){
	const long double factor = 1.055645;
	seq2.pb(0);seq2.pb(1);
	for(int i=2;i<256;++i){
		int x=(int)(factor*seq2.back());
		if(x==seq2.back())++x;
		seq2.pb(x);
	}
}

void InitDevice(){
	build2();
}

int Answer(ll S, ll T){
	ll preS=S&ones,preT=T&ones;
	ll distS=S>>20,distT=T>>20;
	ll pstS=preS+seq2[distS]-1,pstT=preT+seq2[distT]-1;
	//pf("S: %lld %lld %lld\n",preS,distS,pstS);
	//pf("T: %lld %lld %lld\n",preT,distT,pstT);
	if(preT<=preS&&preS<=pstT)return 0;
	if(preS<=preT&&preT<=pstS)return 1;
	return 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7384 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 4 ms 7424 KB Output is correct
4 Correct 5 ms 7460 KB Output is correct
5 Correct 4 ms 7424 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7420 KB Output is correct
8 Correct 4 ms 7376 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 6 ms 7432 KB Output is correct
12 Correct 5 ms 7388 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 22852 KB Output is correct - L = 101711872
2 Correct 191 ms 22844 KB Output is correct - L = 101711872
3 Correct 201 ms 22968 KB Output is correct - L = 100663296
4 Correct 186 ms 22924 KB Output is correct - L = 101711872
5 Correct 540 ms 52596 KB Output is correct - L = 218103808
6 Correct 520 ms 52592 KB Output is correct - L = 219152384
7 Correct 495 ms 52480 KB Output is correct - L = 219152384
8 Correct 503 ms 52336 KB Output is correct - L = 218103808
9 Correct 415 ms 53428 KB Output is correct - L = 229638144
10 Correct 448 ms 53368 KB Output is correct - L = 231735296
11 Correct 454 ms 53568 KB Output is correct - L = 231735296
12 Correct 430 ms 53712 KB Output is correct - L = 231735296
13 Correct 488 ms 53140 KB Output is correct - L = 223346688
14 Correct 581 ms 52580 KB Output is correct - L = 220200960
15 Correct 214 ms 22904 KB Output is correct - L = 101711872
16 Correct 190 ms 22964 KB Output is correct - L = 101711872
17 Correct 197 ms 22968 KB Output is correct - L = 100663296
18 Correct 464 ms 52700 KB Output is correct - L = 230686720
19 Correct 510 ms 52624 KB Output is correct - L = 230686720
20 Correct 470 ms 52576 KB Output is correct - L = 230686720
21 Correct 495 ms 52664 KB Output is correct - L = 230686720
22 Correct 523 ms 52676 KB Output is correct - L = 230686720
23 Correct 542 ms 52872 KB Output is correct - L = 230686720
24 Correct 504 ms 52840 KB Output is correct - L = 229638144
25 Correct 508 ms 52704 KB Output is correct - L = 228589568
26 Correct 512 ms 52580 KB Output is correct - L = 227540992
27 Correct 550 ms 52580 KB Output is correct - L = 226492416