Submission #342379

#	Time	Username	Problem	Language	Result	Execution time	Memory
342379		rqi	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	115 ms	13572 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;

#define ins insert
#define pb push_back
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bk back()

struct DSU{
	vi e;
	void init(int SZ){
		e = vi(SZ, -1);
	}
	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}
	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};



const int mx = 10005;
const int K = 60;
static int bitnum[mx];
static vi bitsub[mx];

static set<int> adj[mx];

static vi to_binary(ll X){
	vi x;
	for(int i = 0; i < K; i++){
		x.pb((X>>i)&1);
	}
	return x;
}

static ll from_binary(vi x){
	ll X = 0;
	ll curt = 1;
	for(int i = 0; i < K; i++){
		X+=curt*x[i];
		curt*=2;
	}
	return X;
}


////
static int sub[mx];
static void genSub(int node, int prv = -1){
	//cout << "node, prv: " << node << ", " << prv << "\n"; 
	sub[node] = 1;
	for(auto u: adj[node]){
		if(u == prv) continue;
		genSub(u, node);
		sub[node]+=sub[u];
	}
}

static int getCen(int node, int totsz, int prv = -1){
	for(auto u: adj[node]){
		if(u == prv) continue;
		if(sub[u]*2 >= totsz) return getCen(u, totsz, node);
	}
	return node;
}

static void shiftBitNum(int node, int shiftval, int prv = -1){
	bitnum[node] = (bitnum[node]+shiftval) % K;
	for(auto u: adj[node]){
		if(u == prv) continue;
		shiftBitNum(u, shiftval, node);
	}
}

//int listnum[mx];
static bool active[mx];
static vi activetaken; //what nodes in list1 to take. Take a certain number

static void findActive(int node, int tot, int prv = -1){
	if(sz(activetaken) < tot) activetaken.pb(node);

	for(auto u: adj[node]){
		if(u == prv) continue;
		if(!active[u]) continue;
		findActive(u, tot, node);
	}
}

static vi curcomp;

static void genCurComp(int node, int prv = -1){
	curcomp.pb(node);
	for(auto u: adj[node]){
		if(u == prv) continue;
		genCurComp(u, node);
	}
}

static void solve(int c){
	// cout << "c: " << c << "\n";
	// cout.flush();

	genSub(c);
	int n = sub[c];
	assert(n >= K);
	
	int cen = getCen(c, sub[c]);
	pair<vi, int> list1 = mp(vi{}, 1); pair<vi, int> list2 = mp(vi{}, 1);
	for(auto u: adj[cen]){
		if(sub[u] > sub[cen]){
			sub[u] = n-sub[cen]; //rooted at cen
		}
	}

	vpi sortsubs;
	for(auto u: adj[cen]){
		sortsubs.pb(mp(sub[u], u));
	}
	sort(sortsubs.rbegin(), sortsubs.rend());

	for(auto u: sortsubs){
		list2.f.pb(u.s);
		list2.s+=u.f;
		if(list1.s < list2.s){
			swap(list1, list2);
		}
	}

	// for(auto u: list1.f) listnum[u] = 1;
	// for(auto u: list2.f) listnum[u] = 2;

	vi comp1, comp2; //comp2 does not include cen
	comp1.pb(cen);
	for(auto u: list1.f){
		curcomp.clear();
		genCurComp(u, cen);
		for(auto z: curcomp){
			comp1.pb(z);
		}
	}
	for(auto u: list2.f){
		curcomp.clear();
		genCurComp(u, cen);
		for(auto z: curcomp){
			comp2.pb(z);
		}
	}
	vi COMP = comp1;
	for(auto u: comp2) COMP.pb(u);

	if(list1.s >= K && list2.s >= K){
		//cout << cen << " Case 1:\n"; 
		for(auto u: list2.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);
		for(auto u: list2.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}

		int cenans = bitnum[cen];
		bitsub[cen].clear();

		for(auto u: list1.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);
		int shiftval = (cenans-bitnum[cen]+K) % K;
		shiftBitNum(cen, shiftval);
		for(auto u: list1.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}
	}
	else if(list1.s >= K && list2.s < K){
		//cout << cen << " Case 2:\n"; 
		for(auto u: list2.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);

		for(auto u: list2.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}

		for(auto u: bitsub[cen]){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp2));
		for(auto u: bitsub[cen]){
			active[u] = 0;
		}
		vi curbitnums(K, 0);
		for(auto u: activetaken){
			curbitnums[bitnum[u]] = 1;
		}
		vi bitnumsleft;
		for(int i = 0; i < K; i++){
			if(curbitnums[i] == 0){
				bitnumsleft.pb(i);
			}
		}

		vi compleft;
		for(auto u: list2.f){
			curcomp.clear();
			genCurComp(u, cen);
			for(auto z: curcomp){
				compleft.pb(z);
			}
		}

		assert(sz(compleft) == sz(bitnumsleft));
		for(int i = 0; i < sz(compleft); i++){
			bitnum[compleft[i]] = bitnumsleft[i];
		}

		for(auto u: compleft){
			activetaken.pb(u);
		}

		for(auto u: compleft){
			bitsub[u] = activetaken;
		}
	}
	else if(list1.s < K && list2.s < K){
		//cout << cen << " Case 3:\n"; 

		for(auto u: comp1){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp2));
		vi comp1sub = activetaken;
		for(auto u: comp1){
			active[u] = 0;
		}

		for(auto u: comp2){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp1)+1);
		vi comp2sub = activetaken; //has cen in it (shouldn't be there)
		for(auto u: comp2){
			active[u] = 0;
		}

		for(int i = 0; i < sz(comp2sub); i++){
			if(comp2sub[i] == cen){
				comp2sub.erase(comp2sub.begin()+i);
				break;
			}
		}

		vi allK = comp1;
		for(auto z: comp2sub){
			allK.pb(z);
		}
		assert(sz(allK) == K);
		for(auto u: comp1){
			bitsub[u] = allK;
		}
		allK = comp2;
		for(auto z: comp1sub){
			allK.pb(z);
		}
		assert(sz(allK) == K);
		for(auto u: comp2){
			bitsub[u] = allK;
		}

		for(int i = 0; i < sz(comp1sub); i++){
			bitnum[comp1sub[i]] = i;
		}
		for(int j = 0; j < sz(comp2sub); j++){
			bitnum[comp2sub[j]] = sz(comp1sub)+j;
		}
		vi numlefts;
		for(int i = sz(comp1sub)+sz(comp2sub); i < K; i++){
			numlefts.pb(i);
		}
		vi numleftscopy = numlefts;

		for(auto u: comp1){
			active[u] = 1;
		}
		for(auto u: comp1sub){
			active[u] = 0;
		}
		for(auto u: comp1){
			if(!active[u]) continue;
			assert(sz(numlefts));
			bitnum[u] = numlefts.bk;
			numlefts.pop_back();
		}
		for(auto u: comp1){
			active[u] = 0;
		}

		numlefts = numleftscopy;
		for(auto u: comp2){
			active[u] = 1;
		}
		for(auto u: comp2sub){
			active[u] = 0;
		}
		for(auto u: comp2){
			if(!active[u]) continue;
			assert(sz(numlefts));
			bitnum[u] = numlefts.bk;
			numlefts.pop_back();
		}
		for(auto u: comp2){
			active[u] = 0;
		}
	}
	else assert(0 == 1);

	// cout << "cen: " << cen << "\n";
	// for(auto u: COMP){
	// 	cout << u << " " << bitnum[u] << "\n";
	// }
	// for(auto u: COMP){
	// 	cout << u << ": ";
	// 	for(auto z: bitsub[u]){
	// 		cout << z << " ";
	// 	}
	// 	cout << "\n";
	// }
}

///

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	DSU dsu;
	dsu.init(N+5);
	for(int i = 0; i < M; i++){
		if(dsu.unite(A[i], B[i])){
			//cout << A[i] << " " << B[i] << "\n";
			adj[A[i]].ins(B[i]);
			adj[B[i]].ins(A[i]);
		}
	}
	solve(0);
	vi x = to_binary(X);
	for(int i = 0; i < N; i++){
		MessageBoard(i, x[bitnum[i]]);
	}

	// for(int i = 0; i < N; i++){
	// 	cout << i << ": " << bitnum[i] << "\n";
	// }
	// for(int i = 0; i < N; i++){
	// 	cout << i << ": ";
	// 	for(auto u: bitsub[i]){
	// 		cout << u << " ";
	// 	}
	// 	cout << "\n";
	// }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;

#define ins insert
#define pb push_back
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bk back()

struct DSU{
	vi e;
	void init(int SZ){
		e = vi(SZ, -1);
	}
	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}
	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};



const int mx = 10005;
const int K = 60;
static int bitnum[mx];
static vi bitsub[mx];

static set<int> adj[mx];

static vi to_binary(ll X){
	vi x;
	for(int i = 0; i < K; i++){
		x.pb((X>>i)&1);
	}
	return x;
}

static ll from_binary(vi x){
	ll X = 0;
	ll curt = 1;
	for(int i = 0; i < K; i++){
		X+=curt*x[i];
		curt*=2;
	}
	return X;
}


////
static int sub[mx];
static void genSub(int node, int prv = -1){
	//cout << "node, prv: " << node << ", " << prv << "\n"; 
	sub[node] = 1;
	for(auto u: adj[node]){
		if(u == prv) continue;
		genSub(u, node);
		sub[node]+=sub[u];
	}
}

static int getCen(int node, int totsz, int prv = -1){
	for(auto u: adj[node]){
		if(u == prv) continue;
		if(sub[u]*2 >= totsz) return getCen(u, totsz, node);
	}
	return node;
}

static void shiftBitNum(int node, int shiftval, int prv = -1){
	bitnum[node] = (bitnum[node]+shiftval) % K;
	for(auto u: adj[node]){
		if(u == prv) continue;
		shiftBitNum(u, shiftval, node);
	}
}

//int listnum[mx];
static bool active[mx];
static vi activetaken; //what nodes in list1 to take. Take a certain number

static void findActive(int node, int tot, int prv = -1){
	if(sz(activetaken) < tot) activetaken.pb(node);

	for(auto u: adj[node]){
		if(u == prv) continue;
		if(!active[u]) continue;
		findActive(u, tot, node);
	}
}

static vi curcomp;

static void genCurComp(int node, int prv = -1){
	curcomp.pb(node);
	for(auto u: adj[node]){
		if(u == prv) continue;
		genCurComp(u, node);
	}
}

static void solve(int c){
	// cout << "c: " << c << "\n";
	// cout.flush();

	genSub(c);
	int n = sub[c];
	assert(n >= K);
	
	int cen = getCen(c, sub[c]);
	pair<vi, int> list1 = mp(vi{}, 1); pair<vi, int> list2 = mp(vi{}, 1);
	for(auto u: adj[cen]){
		if(sub[u] > sub[cen]){
			sub[u] = n-sub[cen]; //rooted at cen
		}
	}

	vpi sortsubs;
	for(auto u: adj[cen]){
		sortsubs.pb(mp(sub[u], u));
	}
	sort(sortsubs.rbegin(), sortsubs.rend());

	for(auto u: sortsubs){
		list2.f.pb(u.s);
		list2.s+=u.f;
		if(list1.s < list2.s){
			swap(list1, list2);
		}
	}

	// for(auto u: list1.f) listnum[u] = 1;
	// for(auto u: list2.f) listnum[u] = 2;

	vi comp1, comp2; //comp2 does not include cen
	comp1.pb(cen);
	for(auto u: list1.f){
		curcomp.clear();
		genCurComp(u, cen);
		for(auto z: curcomp){
			comp1.pb(z);
		}
	}
	for(auto u: list2.f){
		curcomp.clear();
		genCurComp(u, cen);
		for(auto z: curcomp){
			comp2.pb(z);
		}
	}
	vi COMP = comp1;
	for(auto u: comp2) COMP.pb(u);

	if(list1.s >= K && list2.s >= K){
		//cout << cen << " Case 1:\n"; 
		for(auto u: list2.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);
		for(auto u: list2.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}

		int cenans = bitnum[cen];
		bitsub[cen].clear();

		for(auto u: list1.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);
		int shiftval = (cenans-bitnum[cen]+K) % K;
		shiftBitNum(cen, shiftval);
		for(auto u: list1.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}
	}
	else if(list1.s >= K && list2.s < K){
		//cout << cen << " Case 2:\n"; 
		for(auto u: list2.f){
			adj[cen].erase(u);
			adj[u].erase(cen);
		}
		solve(cen);

		for(auto u: list2.f){
			adj[cen].ins(u);
			adj[u].ins(cen);
		}

		for(auto u: bitsub[cen]){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp2));
		for(auto u: bitsub[cen]){
			active[u] = 0;
		}
		vi curbitnums(K, 0);
		for(auto u: activetaken){
			curbitnums[bitnum[u]] = 1;
		}
		vi bitnumsleft;
		for(int i = 0; i < K; i++){
			if(curbitnums[i] == 0){
				bitnumsleft.pb(i);
			}
		}

		vi compleft;
		for(auto u: list2.f){
			curcomp.clear();
			genCurComp(u, cen);
			for(auto z: curcomp){
				compleft.pb(z);
			}
		}

		assert(sz(compleft) == sz(bitnumsleft));
		for(int i = 0; i < sz(compleft); i++){
			bitnum[compleft[i]] = bitnumsleft[i];
		}

		for(auto u: compleft){
			activetaken.pb(u);
		}

		for(auto u: compleft){
			bitsub[u] = activetaken;
		}
	}
	else if(list1.s < K && list2.s < K){
		//cout << cen << " Case 3:\n"; 

		for(auto u: comp1){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp2));
		vi comp1sub = activetaken;
		for(auto u: comp1){
			active[u] = 0;
		}

		for(auto u: comp2){
			active[u] = 1;
		}
		activetaken.clear();
		findActive(cen, K-sz(comp1)+1);
		vi comp2sub = activetaken; //has cen in it (shouldn't be there)
		for(auto u: comp2){
			active[u] = 0;
		}

		for(int i = 0; i < sz(comp2sub); i++){
			if(comp2sub[i] == cen){
				comp2sub.erase(comp2sub.begin()+i);
				break;
			}
		}

		vi allK = comp1;
		for(auto z: comp2sub){
			allK.pb(z);
		}
		assert(sz(allK) == K);
		for(auto u: comp1){
			bitsub[u] = allK;
		}
		allK = comp2;
		for(auto z: comp1sub){
			allK.pb(z);
		}
		assert(sz(allK) == K);
		for(auto u: comp2){
			bitsub[u] = allK;
		}

		for(int i = 0; i < sz(comp1sub); i++){
			bitnum[comp1sub[i]] = i;
		}
		for(int j = 0; j < sz(comp2sub); j++){
			bitnum[comp2sub[j]] = sz(comp1sub)+j;
		}
		vi numlefts;
		for(int i = sz(comp1sub)+sz(comp2sub); i < K; i++){
			numlefts.pb(i);
		}
		vi numleftscopy = numlefts;

		for(auto u: comp1){
			active[u] = 1;
		}
		for(auto u: comp1sub){
			active[u] = 0;
		}
		for(auto u: comp1){
			if(!active[u]) continue;
			assert(sz(numlefts));
			bitnum[u] = numlefts.bk;
			numlefts.pop_back();
		}
		for(auto u: comp1){
			active[u] = 0;
		}

		numlefts = numleftscopy;
		for(auto u: comp2){
			active[u] = 1;
		}
		for(auto u: comp2sub){
			active[u] = 0;
		}
		for(auto u: comp2){
			if(!active[u]) continue;
			assert(sz(numlefts));
			bitnum[u] = numlefts.bk;
			numlefts.pop_back();
		}
		for(auto u: comp2){
			active[u] = 0;
		}
	}
	else assert(0 == 1);

	// cout << "cen: " << cen << "\n";
	// for(auto u: COMP){
	// 	cout << u << " " << bitnum[u] << "\n";
	// }
	// for(auto u: COMP){
	// 	cout << u << ": ";
	// 	for(auto z: bitsub[u]){
	// 		cout << z << " ";
	// 	}
	// 	cout << "\n";
	// }
}

///

static vi bitval;
static bool inAnsComp[mx];
static int cur;
set<pi> elist;
static void tour(int node, int prv = -1){
	for(auto u: adj[node]){
		if(u == prv) continue;
		if(u != node);
		assert(elist.count(mp(cur, u)));
		bitval[bitnum[u]] = Move(u);
		cur = u;
		tour(u, node);
		assert(elist.count(mp(cur, node)));
		Move(node);
		cur = node;
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	cur = P;
	DSU dsu;
	dsu.init(N+5);
	for(int i = 0; i < M; i++){
		elist.ins(mp(A[i], B[i]));
		elist.ins(mp(B[i], A[i]));
		if(dsu.unite(A[i], B[i])){
			adj[A[i]].ins(B[i]);
			adj[B[i]].ins(A[i]);
		}
	}
	solve(0);

	assert(sz(bitsub[P]) == K);
	bitval = vi(K, 0);
	bitval[bitnum[P]] = V;
	for(auto u: bitsub[P]){
		inAnsComp[u] = 1;
	}
	for(int i = 0; i < N; i++){
		vi eraselist;
		for(auto u: adj[i]){
			if(!inAnsComp[u]) eraselist.pb(u); 
		}
		for(auto u: eraselist){
			adj[i].erase(u);
		}
	}

	tour(P);
	
	return from_binary(bitval);
}

Compilation message (stderr)

Joi.cpp:57:11: warning: 'll from_binary(vi)' defined but not used [-Wunused-function]
   57 | static ll from_binary(vi x){
      |           ^~~~~~~~~~~

Ioi.cpp:49:11: warning: 'vi to_binary(ll)' defined but not used [-Wunused-function]
   49 | static vi to_binary(ll X){
      |           ^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17