제출 #564411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564411		8e7	즐거운 행로 (APIO20_fun)	C++17	31 / 100	129 ms	16476 KiB

fun

//Challenge: Accepted
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dis[maxn];
vector<pii> comp[3];
int getsize(int u, int v) {
	return attractionsBehind(u, v);
}

int recur[maxn];
int solve(vector<int> v) {
	int root = v[0], siz = v.size();

	for (int i = 1;i < siz;i++) {
		if (getsize(root, v[i]) * 2 > siz) {
			root = v[i];
		}
	}
	vector<int> con;
	for (int i:v) {
		if (i == root) continue;
		recur[i] = 0;
		dis[i] = hoursRequired(root, i);
		if (dis[i] == 1) {
			con.push_back(i);
		}
	}
	for (int i = 1;i < con.size();i++) {
		for (int j:v) {
			if (j != root && !recur[j]) {
				//debug(j, con[i], getsize(j, con[i], d));
				if (hoursRequired(j, con[i]) < dis[j]) {
					recur[j] = i;
				}
			}
		}
	}
	for (int i = 0;i < con.size();i++) {
		for (int j:v) {
			if (j != root && recur[j] == i) {
				comp[i].push_back({dis[j], j});	
			}
		}
	}
	return root;
}


vector<int> createFunTour(int N, int Q) {
	vector<int> ini, ret;
	for (int i = 0;i < N;i++) ini.push_back(i);
	int root = solve(ini);
	sort(comp, comp + 3, [&] (vector<pii> x, vector<pii> y){return x.size() < y.size();});
	for (int i = 0;i < 3;i++) sort(comp[i].begin(), comp[i].end());	
	if (N == 1) {
		ret.push_back(root);
		return ret;
	}
	int cur = 2, iter = N - 1;
	auto nxt = [&] (int v1, int v2) {
		if (!comp[v1].size()) cur = v2;
		else if (!comp[v2].size()) cur = v1;
		else if (comp[v1].back().ff > comp[v2].back().ff) cur = v1;
		else cur = v2;
	};
	if (comp[0].size() + comp[1].size() >= comp[2].size()) {
		if (comp[0].size() && comp[0].back().ff > comp[cur].back().ff) cur = 0;
		if (comp[1].size() && comp[1].back().ff > comp[cur].back().ff) cur = 1;
	} else {
		comp[1].insert(comp[1].end(), comp[0].begin(), comp[0].end());
		comp[0].clear();
	}
	int same = 0, si = 0;
	for (int i = 0;i < iter;i++) {
		ret.push_back(comp[cur].back().ss);
		comp[cur].pop_back();
		
		int c0 = comp[0].size(), c1 = comp[1].size(), c2 = comp[2].size();
		if (!same) {
			if (c0 + c1 == c2) same = 1, si = 2;
			else if (c0 + c2 == c1) same = 1, si = 1;
			else if (c1 + c2 == c0) same = 1, si = 0;
		}
		if (c0 + c1 <= c2 && cur != 2 && si == 2) cur = 2;
		else if (c0 + c2 <= c1 && cur != 1 && si == 1) cur = 1;
		else if (c1 + c2 <= c0 && cur != 0 && si == 0 && same) cur = 0;
		else {
			if (cur == 0) nxt(1, 2);
			else if (cur == 1) nxt(0, 2);
			else nxt(0, 1);
		}
	}
	ret.push_back(root);
	return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp: In function 'int solve(std::vector<int>)':
fun.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 1;i < con.size();i++) {
      |                 ~~^~~~~~~~~~~~
fun.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0;i < con.size();i++) {
      |                 ~~^~~~~~~~~~~~

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