Submission #568821

#	Time	Username	Problem	Language	Result	Execution time	Memory
568821		Zanite	Fun Tour (APIO20_fun)	C++17	31 / 100	134 ms	16336 KiB

fun

// You can't change other people; you can only change yourself.
 
#include "fun.h"
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
// Namespaces
#define yume	using
#define wo		namespace
#define kanaeyo	std
#define nazotte	__gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
 
// Data types
using i8	= __int128;
using ll	= long long;
using si	= short int;
using ld	= long double;
 
// Pairs
using pi8	= pair<i8, i8>;
using pll	= pair<ll, ll>;
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second
 
// PBDS
template<typename T>
using ordered_set	= tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
// Quick macro functions
#define sqr(x)			((x)*(x))
#define pow2(x)			(1ll << (x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(x, a)	cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
 
// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
 
// Constants
const ll ModA	= 998244353;
const ll ModC	= 1e9 + 7;
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;
 
vector<int> createFunTour(int N, int Q) {
	// corner case
	if (N == 2) {return {0, 1};}
 
	// Find centroid of tree
	int minSubtree = iINF, centroid = -1;
	int _0 = attractionsBehind(1, 0);
	if (_0 >= (N+1)/2) {
		minSubtree = _0;
		centroid = 0;
	}
	for (int i = 1; i < N; i++) {
		int cur = attractionsBehind(0, i);
		if (cur >= (N+1)/2 && cur < minSubtree) {
			centroid = i;
			minSubtree = cur;
		}
	}
	//printf("Centroid: %d\n", centroid);
 
	// Find distance of all nodes to centroid
	// Also find the 'groups' of nodes from centroid
	vector<int> groupRep, groupRepSize;
	vector<vector<pii>> groups;
	vector<int> dist(N);
	for (int i = 0; i < N; i++) {
		if (i == centroid) continue;
		dist[i] = hoursRequired(centroid, i);
		if (dist[i] == 1) {
			groupRep.push_back(i);
			groups.push_back({{1, i}});
		}
	}
	for (auto i : groupRep) {
		groupRepSize.push_back(attractionsBehind(centroid, i));
	}
	assert(groupRep.size() > 1);
	//for (auto i : dist) cout << i << ' '; cout << '\n';
	//for (auto i : groupRep) cout << i << ' '; cout << '\n';
	//for (auto i : groupRepSize) cout << i << ' '; cout << '\n';
 
	// Find which group each node belongs to
	for (int i = 0; i < N; i++) {
		if (dist[i] <= 1) continue;
		bool found = 0;
		for (int g = 0; g < groupRep.size()-1; g++) {
			//printf("Checking %d in group %d\n", i, groupRep[g]);
			if (hoursRequired(i, groupRep[g]) == dist[i] - 1) {
				groups[g].push_back({dist[i], i});
				found = 1;
				break;
			}
		}
		if (!found) {
			groups.back().push_back({dist[i], i});
		}
	}
 
	for (auto &g : groups) {
		sort(g.begin(), g.end());
		//for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
	}
 
	// construct fun tour!
	vector<int> ans;
	int lastPicked = -1;
	for (int i = 1; i < N; i++) {
		//printf("Last picked %d\n", lastPicked);
		//for (auto g : groups) {
		//	for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
		//}
		if (groups.size() == 3) {
			int mx = -1, mxIndex = -1;
			for (int g = 0; g < 3; g++) {
				if (g == lastPicked) continue;
				if (groups[g].back().fi > mx) {
					mx = groups[g].back().fi;
					mxIndex = g;
				}
			}
			ans.push_back(groups[mxIndex].back().se);
			groups[mxIndex].pop_back();
			lastPicked = mxIndex;
 
			int sz[] = {(int)groups[0].size(), (int)groups[1].size(), (int)groups[2].size()};
			bool merge = 0;
			if (sz[0] + sz[1] == sz[2]) {
				merge = 1;
				swap(groups[0], groups[2]);
				if (lastPicked == 0) {lastPicked = 1;}
				else if (lastPicked == 2) {lastPicked = 0;}
			} else if (sz[0] + sz[2] == sz[1]) {
				merge = 1;
				swap(groups[0], groups[1]);
				if (lastPicked == 2) {lastPicked = 1;}
				else if (lastPicked == 1) {lastPicked = 0;}
			} else if (sz[1] + sz[2] == sz[0]) {
				merge = 1;
				if (lastPicked == 2) {lastPicked = 1;}
			}
			if (merge) {
				for (auto x : groups[2]) {groups[1].push_back(x);}
				groups.pop_back();
				sort(groups.back().begin(), groups.back().end());
			}
		} else {
			for (int g = 0; g < 2; g++) {
				if (lastPicked == g) {continue;}
				ans.push_back(groups[g].back().se);
				groups[g].pop_back();
				lastPicked = g;
				break;
			}
		}
	}
	ans.push_back(centroid);
	//for (auto i : ans) {cout << i << ' ';} cout << '\n';
	return ans;
}
 
//int main() {}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int g = 0; g < groupRep.size()-1; g++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34