Submission #1026651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026651		Antekb	City (JOI17_city)	C++17	18 / 100	772 ms	135488 KiB

Encoder

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif


#include "Encoder.h"

const int N=3e5+5;
vi E[N];
vi code[N];

pair<int, vi > dfs(int v, int p){
	priority_queue<pair<int, vi>, vector<pair<int, vi>>, greater<pair<int, vi> > > Q;
	for(int u:E[v]){
		if(u!=p){
			Q.push(dfs(u, v));
		}
	}
	if(Q.size()==0){
		return {0, {v}};
	}
	else if(Q.size()==1){
		auto child=Q.top();
		for(int i:child.nd){
			code[i].push_back(0);
		}
		child.st++;
		child.nd.pb(v);
		return child;
	}
	else{
		while(Q.size()>1){
			auto child1=Q.top();
			Q.pop();
			auto child2=Q.top();
			Q.pop();
			for(int i:child1.nd)code[i].pb(0);
			for(int i:child2.nd)code[i].pb(1);
			for(int i:child1.nd)child2.nd.pb(i);
			child2.st++;
			Q.push(child2);
		}
		auto child=Q.top();
		child.nd.pb(v);
		return child;
	}
}

void Encode(int n, int A[], int B[])
{
	/*for (int i = 0; i < N; ++i) {
		Code(i, 0LL);
	}*/
	for(int i=0; i<n-1; i++){
		E[A[i]].pb(B[i]);
		E[B[i]].pb(A[i]);
	}
	int len=dfs(0, -1).st;
	deb(len);
	int LEN=38;
	assert(len<LEN);
	for(int i=0; i<n; i++){
		reverse(all(code[i]));
		//deb(i, code[i]);
		code[i].pb(0);
		code[i].resize(LEN, 1);
		ll code_num=0;
		for(int j=0; j<LEN; j++){
			code_num+=(ll(code[i][j])<<j);
		}
		//deb(i, code[i]);
		Code(i, code_num);
	}
}

Device

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

#include "Device.h"

void InitDevice()
{
}

bool substring(vi A, vi B){
	if(B.size()<A.size())return 0;
	B.resize(A.size());
	return (A==B);
}

int Answer(long long S, long long T)
{
	int LEN=38;
	vi codeS, codeT;
	for(int j=0; j<LEN; j++){
		codeS.pb((S>>j)&1);
		codeT.pb((T>>j)&1);
	}
	while(codeS.back()==1)codeS.pop_back();
	codeS.pop_back();
	while(codeT.back()==1)codeT.pop_back();
	codeT.pop_back();
	//deb(codeS, codeT);
	if(substring(codeT, codeS))return 0;
	if(substring(codeS, codeT))return 1;
	return 2;
}

Compilation message (stderr)

Encoder.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Encoder.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Encoder.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Encoder.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Encoder.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~

Device.cpp:18:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Device.cpp:18:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Device.cpp:18:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Device.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Device.cpp:20:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~

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