Submission #486226

#	Time	Username	Problem	Language	Result	Execution time	Memory
486226		kig9981	City (JOI17_city)	C++17	8 / 100	150 ms	15000 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
vector<int> adj[250000];
int node_cnt, W[250000], parent[250000], level[250000], F[250000], num[250000], R[250000];
 
long long compress(long long a, long long b, long long c) {return (a<<18)|(b<<9)|c;}
 
void dfs(int c)
{
	W[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		parent[n]=c;
		dfs(n);
		W[c]+=W[n];
	}
}
 
void dfs2(int c)
{
	num[c]=node_cnt++;
	for(auto n: adj[c]) if(level[n]==level[c] && parent[n]==c) {
		F[n]=F[c];
		dfs2(n);
	}
	R[c]=node_cnt-1;
}
 
void Encode(int N, int A[], int B[])
{
	priority_queue<pair<int,int>> Q;
	for(int i=0;i<N-1;i++) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(0);
	for(int i=0;i<N;i++) Q.emplace(W[i],i);
	for(int i=1;i<512 && Q.size();i++) {
		int c=Q.top().second;
		Q.pop();
		level[c]=1;
	}
	node_cnt=1; dfs2(0);
	for(int i=1;i<N;i++) if(level[parent[i]]!=level[i]) {
		F[i]=num[parent[i]];
		node_cnt=0; dfs2(i);
	}
	for(int i=0;i<N;i++) {
      assert(F[i]<512 && num[i]<512 && R[i]<512);
      Code(i,compress(F[i],num[i],R[i]));
    }
}

Device

#include "Device.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
tuple<int,int,int> decompress(long long a) {return {(a>>18)&511,(a>>9)&511,a&511};}
 
void InitDevice() {}
 
int Answer(long long S, long long T)
{
	auto[sf,sl,sr]=decompress(S);
	auto[tf,tl,tr]=decompress(T);
	if(sf==tf) {
		if(tl<=sl && sr<=tr) return 0;
		if(sl<=tl && tr<=sr) return 1;
		return 2;
	}
	if(sf==0) {
		if(sl<=tf && tf<=sr) return 1;
	}
	if(tf==0) {
		if(tl<=sf && sf<=tr) return 0;
	}
	return 2;
}

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