제출 #563969

#제출 시각아이디문제언어결과실행 시간메모리
563969hollwo_pelw즐거운 행로 (APIO20_fun)C++17
0 / 100
1 ms300 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; vector<int> createFunTour(int N, int Q) { int centroid = 0, tmp = N; for (int i = 1; i < N; i++) { int siz = attractionsBehind(0, i); if (siz > N / 2 && siz < tmp) centroid = i, tmp = siz; } vector<int> depth(N, 0), group(N, 0); for (int i = 0; i < N; i++) if (i != centroid) { depth[i] = hoursRequired(centroid, i); } vector<int> branch; for (int i = 0; i < N; i++) if (depth[i] == 1) branch.push_back(i); int M = branch.size(); for (int i = 0; i < N; i++) if (i != centroid) { for (int j = 1; j < M; j++) if (hoursRequired(branch[j], i) == depth[i] - 1) { group[i] = j; break; } } vector<vector<int>> list_val(M = 3); for (int i = 0; i < N; i++) if (i != centroid) { list_val[group[i]].push_back(i); } for (int i = 0; i < M; i++) { sort(list_val[i].begin(), list_val[i].end(), [&](const int &i, const int &j){ return depth[i] < depth[j]; }); } vector<int> res, p = {0, 1, 2}; int last = -1; while (true) { sort(p.begin(), p.end(), [&](const int &i, const int &j){ return list_val[i].size() > list_val[j].size(); }); if (list_val[p[0]].size() >= list_val[p[1]].size() + list_val[p[2]].size()) break ; for (int i = 0; i < 3; i++) assert(!list_val[i].empty()); sort(p.begin(), p.end(), [&](const int &i, const int &j){ return depth[list_val[i].back()] > depth[list_val[j].back()]; }); int cur = last == p[0] ? 1 : 0; res.push_back(list_val[cur].back()); list_val[cur].pop_back(), last = cur; } list_val[p[1]].insert(list_val[p[1]].end(), list_val[p[2]].begin(), list_val[p[2]].end()); sort(list_val[p[1]].begin(), list_val[p[1]].end(), [&](const int &i, const int &j){ return depth[i] < depth[j]; }); last = ((int) res.size() >= 2 && group[res[res.size() - 2]] != p[0] && depth[res[res.size() - 2]] > depth[res.back()] && depth[list_val[p[1]].back()] > depth[res.back()] ) ? 1 : 0; for (; list_val[p[last]].size(); last ^= 1) { res.push_back(list_val[p[last]].back()); list_val[p[last]].pop_back(); } res.push_back(centroid); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...