Submission #1080578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080578		Evirir	City (JOI17_city)	C++17	30 / 100	369 ms	57592 KiB

Encoder

#include "Encoder.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

static constexpr ll LG = 18;
static constexpr ll MAXN = 250000;

static vector<vector<int>> adj;
static int tmr = 0;
static vector<ll> in;
static vector<ll> out;
static vector<int> prt, sub;

static void getprt(int u, int p = -1)
{
	sub[u] = 1;
	prt[u] = p;
	for (const auto v : adj[u])
	{
		if (v == p) continue;
		getprt(v, u);
		sub[u] += sub[v];
	}
}

static void dfs(int u, int p = -1)
{
	in[u] = tmr;
	if (adj[u].empty())
	{
		out[u] = tmr;
		return;
	}

	for (const auto v : adj[u])
	{
		dfs(v, u);
		tmr++;
	}
	tmr--;
	if (sz(adj[u]) == 1)
	{
		tmr++;
		out[u] = tmr;
		return;
	}
	out[u] = tmr;
}

static ll arith(ll l, ll r)
{
	return (l + r) * (r - l + 1) / 2;
}

static ll pair2id(ll l, ll r)
{
	l++; r++;
	return arith(MAXN - (l - 1) + 1, MAXN) + r - l + 1;  // pair id 1-indexed
}

void Encode(int n, int a[], int b[])
{
	adj.resize(n);
	in.resize(n);
	out.resize(n);
	prt.resize(n, -1);
	sub.resize(n);
	forn(i,0,n-1)
	{
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	getprt(0);
	forn(u,1,n)
	{
		forn(i,0,sz(adj[u]))
		{
			if (adj[u][i] == prt[u])
			{
				swap(adj[u][i], adj[u].back());
				adj[u].pop_back();
				break;
			}
		}
		sort(all(adj[u]), [](int v1, int v2){ return tie(sub[v1], v1) > tie(sub[v2], v2); });
	}
	dfs(0);
	forn(u,0,n)
	{
		ll c = pair2id(in[u], out[u]);
		Code(u, c);
	}
}

Device

#include "Device.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

static constexpr int LG = 18;
static constexpr int MAXN = 250000;

void InitDevice()
{
}

static ll arith(ll l, ll r)
{
	return (l + r) * (r - l + 1) / 2;
}

static ll pair2id(ll l, ll r)
{
	l++; r++;
	return arith(MAXN - (l - 1) + 1, MAXN) + r - l + 1;  // pair id 1-indexed
}

static pair<ll, ll> id2pair(ll id)
{
	ll sum = 0;
	for (ll L = 0, R = MAXN - 1; L <= R;)
	{
		ll mid = (L + R) / 2;
		if (pair2id(mid, mid) > id) R = mid - 1;
		else if (pair2id(mid, MAXN - 1) < id) L = mid + 1;
		else
		{
			ll id0 = pair2id(mid, mid);
			return {mid, mid + id - id0};
		}
	}
	assert(0);
	return {};
}

int Answer(long long s, long long t)
{
	auto [s1, t1] = id2pair(s);
	auto [s2, t2] = id2pair(t);
	if (s2 <= s1 && t1 <= t2) return 0;
	if (s1 <= s2 && t2 <= t1) return 1;
	return 2;
}

Compilation message (stderr)

Device.cpp: In function 'std::pair<long long int, long long int> id2pair(ll)':
Device.cpp:48:5: warning: unused variable 'sum' [-Wunused-variable]
   48 |  ll sum = 0;
      |     ^~~

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