Submission #1009126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009126		emptypringlescan	City (JOI17_city)	C++17	100 / 100	262 ms	105984 KiB

Encoder

    #include <bits/stdc++.h>
    using namespace std;
    #include "Encoder.h"
    vector<int> adj[2500005];
    long long pre[2500005],pos[2500005];
    vector<int> szs;
    int cur=0,cnt;
    int subsz[2500005];
    void fsz(int x, int p){
    	int sz=1;
    	for(int i:adj[x]){
    		if(i==p) continue;
    		fsz(i,x);
    		sz+=subsz[i];
    	}
    	int lol=*lower_bound(szs.begin(),szs.end(),sz);
    	for(int i=sz+1; i<=lol; i++) adj[x].push_back(cnt),cnt++;
    	pos[x]=lower_bound(szs.begin(),szs.end(),sz)-szs.begin();
      subsz[x]=szs[pos[x]];
    }
    void dfs(int x, int p){
    	cur++;
    	pre[x]=cur;
    	for(int i:adj[x]){
    		if(i!=p) dfs(i,x);
    	}
    }
    void Encode(int n, int u[], int v[]){
      szs.push_back(0);
    	cnt=n;
    	long double x=1.8;
    	for(int i=0; i<400; i++){
    		x*=1.044;
    		szs.push_back((int)x);
    	}
    	for(int i=0; i<n-1; i++){
    		adj[u[i]].push_back(v[i]);
    		adj[v[i]].push_back(u[i]);
    	}
    	fsz(0,-1);
    	dfs(0,-1);
    	for(int i=0; i<n; i++){
    		Code(i,pre[i]<<9ll|pos[i]);
    	}
    }

Device

    #include <bits/stdc++.h>
    using namespace std;
    #include "Device.h"
     
    vector<int> szs;
    void InitDevice(){
    	long double x=1.8;
      szs.push_back(0);
    	for(int i=0; i<400; i++){
    		x*=1.044;
    		szs.push_back((int)x);
    	}
    }
    int Answer(long long a, long long b){
    	long long prea=a>>9ll,posa=a^(prea<<9ll);
    	long long preb=b>>9ll,posb=b^(preb<<9ll);
    	posa=szs[posa]+prea;
    	posb=szs[posb]+preb;
    	if(preb<=prea&&posa<=posb) return 0;
    	else if(prea<=preb&&posb<=posa) return 1;
    	return 2;
    }

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