제출 #564047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
564047		8e7	즐거운 행로 (APIO20_fun)	C++17	10 / 100	86 ms	19464 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);
vector<int> adj[maxn];
int tot;
int dis[18][maxn], dep[maxn], outsiz[18][maxn];

int getsize(int u, int v, int d) {
	for (int i = d-1;i >= 0;i--) {
		if (dis[i][u] > dis[i][v]) return attractionsBehind(u, v) - outsiz[i][u];
	}
	return attractionsBehind(u, v);
}

int recur[maxn];
void solve(vector<int> v, int d) {
	//debug("solve");
	//pary(v.begin(), v.end());
	if (v.size() == 0) return;
	if (v.size() == 1) {
		dep[v[0]] = d;	
		return;	
	}
	int root = v[0], siz = v.size();
	for (int i = 1;i < siz;i++) {
		if (getsize(root, v[i], d) * 2 > siz) {
			root = v[i];
		}
	}
	//debug("root", root);
	dep[root] = d;
	vector<int> con;
	for (int i:v) {
		if (i == root) continue;
		recur[i] = 0;
		dis[d][i] = hoursRequired(root, i);
		if (dis[d][i] == 1) {
			adj[root].push_back(i);
			adj[i].push_back(root);
			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 (getsize(j, con[i], d) * 2 > siz) {
					recur[j] = i;
				}
			}
		}
	}
	vector<vector<int> > rec;
	for (int i = 0;i < con.size();i++) {
		vector<int> tmp;
		int p = getsize(con[i], root, d);
		for (int j:v) {
			if (j != root && recur[j] == i) {
				outsiz[d][j] = p;
				tmp.push_back(j);
			}
		}
		rec.push_back(tmp);
	}
	for (auto i:rec) solve(i, d+1);
}


bool vis[maxn];
pii dfs(int n, int pa, int d) {
	pii ret = {d, n};
	for (int v:adj[n]) {
		if (v != pa && !vis[v]) {
			ret = max(ret, dfs(v, n, d + 1));
		}
	}
	return ret;
}
vector<int> createFunTour(int N, int Q) {
	tot = N;
	int H = hoursRequired(0, N - 1);
	int A = attractionsBehind(0, N - 1);
	vector<int> ini, ret;
	for (int i = 0;i < N;i++) ini.push_back(i);
	solve(ini, 0);
	
	int st = max_element(dis[0], dis[0] + N) - dis[0];
	for (int i = 0;i < N;i++) {
		vis[st] = 1;
		ret.push_back(st);
		int nxt = dfs(st, -1, 0).ss;
		st = nxt;
	}
	/*
	for (int i = 0;i < N;i++) {
		debug(i);
		pary(adj[i].begin(), adj[i].end());
	}
	pary(ret.begin(), ret.end());
	*/
	return ret;
}

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

fun.cpp: In function 'void solve(std::vector<int>, int)':
fun.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 1;i < con.size();i++) {
      |                 ~~^~~~~~~~~~~~
fun.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0;i < con.size();i++) {
      |                 ~~^~~~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:99:6: warning: unused variable 'H' [-Wunused-variable]
   99 |  int H = hoursRequired(0, N - 1);
      |      ^
fun.cpp:100:6: warning: unused variable 'A' [-Wunused-variable]
  100 |  int A = attractionsBehind(0, N - 1);
      |      ^

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