Submission #383176

#	Time	Username	Problem	Language	Result	Execution time	Memory
383176		kshitij_sodani	City (JOI17_city)	C++14	30 / 100	554 ms	44516 KiB

Encoder

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "Encoder.h"

vector<llo> adj[250001];
llo co=0;
llo st[250001];
llo endd[250001];
void dfs(llo no,llo par2=-1){
	st[no]=co;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
		}
	}
	co++;
	endd[no]=co-1;
}

void Encode(int n, int aa[], int bb[])
{

	for(int i=0;i<n-1;i++){
		adj[aa[i]].pb(bb[i]);
		adj[bb[i]].pb(aa[i]);
	}
	dfs(0);
	for (int i = 0; i < n; ++i) {
		Code(i, st[i]+((endd[i]*(endd[i]+1))/2));
	}




}

Device

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "Device.h"

void InitDevice()
{
}
llo val(llo x){
	return ((x*(x+1)))/2;
}
pair<llo,llo> cal(llo t){
	llo ind=-1;
	for(llo j=19;j>=0;j--){
		if(val(ind+(1LL<<j))<=t){
			//cout<<val(ind+(1LL<j))<<",,"<<t<<":"<<j<<endl;
			ind+=(1LL<<j);
		}
	}
	//cout<<t<<":"<<t-val(ind)<<":"<<ind<<endl;
	return {t-val(ind),ind};
}
int Answer(long long S, long long T)
{	llo xx2=250000;
	
	pair<llo,llo> xx=cal(S);
	pair<llo,llo> yy=cal(T);
	//0 if T is parent of S
	//1 if S is parent of T
	if(yy.a>=xx.a and yy.b<=xx.b){
		return 1;
	}
	if(yy.a<=xx.a and yy.b>=xx.b){
		return 0;
	}

	return 2;
}

Compilation message (stderr)

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:31:7: warning: unused variable 'xx2' [-Wunused-variable]
   31 | { llo xx2=250000;
      |       ^~~

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