Submission #1080458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080458		Evirir	City (JOI17_city)	C++17	8 / 100	254 ms	56536 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 int LG = 18;

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

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];
	}
}

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

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


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 sub[v1] > sub[v2]; });
	}
	dfs(0);
	forn(i,0,n)
	{
		ll c = (in[i] << LG) + out[i];
		Code(i, 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;

void InitDevice()
{
}

static pair<ll, ll> getio(ll s)
{
	ll in = s >> LG;
	ll out = s & ((1LL << LG) - 1);
	return {in, out};
}

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

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