Submission #486236

#	Time	Username	Problem	Language	Result	Execution time	Memory
486236		kig9981	City (JOI17_city)	C++17	8 / 100	185 ms	15088 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=1;i<N;i++) Q.emplace(W[i],i); level[0]=1;
	for(int i=1;i<512 && Q.size();i++) {
		int c=Q.top().second;
		Q.pop();
		level[c]=1;
	}
	node_cnt=0; dfs2(0); R[0]=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++) 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)
{
	if(S==0) return 1;
	if(T==0) return 0;
	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;
}

Compilation message (stderr)

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |  for(int i=1;i<N;i++) Q.emplace(W[i],i); level[0]=1;
      |  ^~~
Encoder.cpp:47:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   47 |  for(int i=1;i<N;i++) Q.emplace(W[i],i); level[0]=1;
      |                                          ^~~~~

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