Submission #218113

#	Time	Username	Problem	Language	Result	Execution time	Memory
218113		dorijanlendvaj	City (JOI17_city)	C++14	30 / 100	571 ms	71456 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;
using ll=long long;
const char en='\n';

vi ch[250000];
bool bio[250000];
int cu,ind[250000],r[250000];

void dfs(int i)
{
	bio[i]=1;
	ind[i]=cu++;
	for (auto a: ch[i]) if (!bio[a]) dfs(a);
	r[i]=cu;
}

ll to(pair<ll,ll> a)
{
	return a.y*(a.y-1)/2+a.x;
}

void Encode(int N, int A[], int B[])
{
	for (int i = 0; i < N-1; ++i) {
		ch[A[i]].pb(B[i]);
		ch[B[i]].pb(A[i]);
	}
	dfs(0);
	for (int i=0;i<N;++i)
	{
		//cout<<i<<' '<<ind[i]<<' '<<r[i]<<' '<<to({ind[i],r[i]})<<en;
		Code(i,to({ind[i],r[i]}));
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;
using ll=long long;
const char en='\n';

void InitDevice()
{
}

pair<ll,ll> from(ll x)
{
	ll lo=0,hi=260000;
	while (lo<hi)
	{
		ll mid=(lo+hi+1)/2;
		if (x>=mid*(mid-1)/2) lo=mid;
		else hi=mid-1;
	}
	return {x-lo*(lo-1)/2,lo};
}

int Answer(long long S, long long T)
{
	auto p1=from(S),p2=from(T);
	if (p1.x>=p2.x && p1.x<p2.y)
	{
		//cout<<S<<' '<<T<<' '<<0<<en;
		return 0;
	}
	if (p2.x>=p1.x && p2.x<p1.y)
	{
		//cout<<S<<' '<<T<<' '<<1<<en;
		return 1;
	}
	//cout<<S<<' '<<T<<' '<<2<<en;
	return 2;
}

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