# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
674719 |
2022-12-26T01:22:43 Z |
vjudge1 |
Fun Tour (APIO20_fun) |
C++17 |
|
409 ms |
23232 KB |
#include"fun.h"
#include<bits/stdc++.h>
int n;
namespace Task1{
const int N=25;
int dis[N][N],dp[1<<20][20],pre[1<<20][20];
std::vector<int> solve(int n){
std::vector<int> ans;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++){
dis[i][j]=dis[j][i]=hoursRequired(i,j);
}
for(int i=0;i<n;++i)dp[1<<i][i]=1e9;
for(int i=1;i<n;++i)
for(int S=1;S<1<<n;++S)if(__builtin_popcount(S)==i)
for(int u=0;u<n;++u)if((S>>u)&1)
for(int v=0;v<n;++v)if(!((S>>v)&1))
if(dp[S][u]>=dis[u][v]&&dp[S|(1<<v)][v]<dis[u][v]){
dp[S|(1<<v)][v]=dis[u][v];
pre[S|(1<<v)][v]=u;
}
for(int i=0;i<n;++i)if(dp[(1<<n)-1][i]<1e9){
int j,s=(1<<n)-1;
while(s){
ans.push_back(i);
j=pre[s][i],s^=1<<i,i=j;
}
std::reverse(ans.begin(),ans.end());
return ans;
}
assert(0);
}
}
namespace Task0{
inline bool cmp(const std::pair<int,int> &a,const std::pair<int,int> &b){
return a.second<b.second;
}
int find(int rt){
std::vector<int> s(n);
for(int i=0;i<n;i++)s[i]=attractionsBehind(rt,i);
bool fl=true;
for(int i=0;i<n;i++)fl&=s[i]<=n/2;
if(fl)return rt;
int min=INT_MAX,cho=-1;
for(int i=0;i<n;i++)if(s[i]>n/2&&s[i]<min){
min=s[i],cho=i;
}
return cho;
}
inline void sort(std::vector<std::pair<int,int>> &a,std::vector<std::pair<int,int>> &b,std::vector<std::pair<int,int>> &c){
if(a.size()<c.size())std::swap(a,c);
if(a.size()<b.size())std::swap(a,b);
if(b.size()<c.size())std::swap(b,c);
}
std::vector<std::pair<int,int>> build(std::vector<std::pair<int,int>> a,std::vector<std::pair<int,int>> b,std::vector<std::pair<int,int>> c,int u){
std::vector<std::pair<int,int>> ans;
sort(a,b,c);
if(a.size()&&b.size()){
if(cmp(a.back(),b.back())&&b.size()+c.size()>=a.size())std::swap(a,b);
}
while(a.size()||b.size()||c.size()){ //a褰撳墠,b涓婁竴娆?c鍓╀笅鐨?
#ifdef local
printf("(%d %d) (%d %d) (%d %d)\n",
a.size()?a.back().first:-1,a.size()?a.back().second:-1,
b.size()?b.back().first:-1,b.size()?b.back().second:-1,
c.size()?c.back().first:-1,c.size()?c.back().second:-1);
#endif
if(a.size()>b.size()+c.size()&&c.size()){
#ifdef local
printf("merge !!\n");
#endif
b.insert(b.end(),c.begin(),c.end()),c.clear();
std::sort(b.begin(),b.end(),cmp);
// for(const auto &x:b)printf("> %d %d\n",x.first,x.second);
if(b.size()&&ans.size()&&cmp(ans.back(),b.back())){
ans.push_back(b.back()),b.pop_back();
}
}
if(!c.size()){ //cross
if(!a.size())a.push_back({u,0}),u=-1;
ans.push_back(a.back()),a.pop_back();
std::swap(a,b);
continue;
}
if(cmp(a.back(),c.back()))std::swap(a,c);
ans.push_back(a.back()),a.pop_back();
std::swap(a,b);
if(c.size()&&a.size()<c.size())std::swap(a,c);
}
if(~u)ans.push_back({u,0});
#ifdef local
for(const auto &x:ans)printf("> %d %d\n",x.first,x.second);
#endif
return ans;
}
std::vector<int> solve(int u){
// printf("solve %d\n",u);
std::vector<int> ret,du(n),dv(n),G;
for(int i=0;i<n;i++)if(i!=u&&hoursRequired(u,i)==1)G.push_back(i);
std::vector<std::pair<int,int>> ans,S[3];
for(int i=0;i<n;i++)if(i!=u)du[i]=hoursRequired(G[0],i);
for(int i=0;i<n;i++)if(i!=u)dv[i]=hoursRequired(G[1],i);
for(int i=0;i<n;i++)if(i!=u){
if(du[i]<dv[i])S[0].push_back({i,du[i]+1});
if(du[i]>dv[i])S[1].push_back({i,dv[i]+1});
if(du[i]==dv[i])S[2].push_back({i,du[i]-1});
}
for(int fl=0;fl<G.size();fl++){
std::sort(S[fl].begin(),S[fl].end(),cmp);
}
#ifdef local
for(int fl=0;fl<G.size();fl++){
printf("[%d] => ",fl);
for(auto x:S[fl])printf("(%d,%d) ",x.first,x.second);
puts("");
}
#endif
ans=build(S[0],S[1],S[2],u);
for(const auto &it:ans)ret.push_back(it.first);
return ret;
}
std::vector<int> solve(){
return solve(find(rand()%n));
}
}
std::vector<int> createFunTour(int N,int Q){
n=N;
if(n<=17)return Task1::solve(n);
return Task0::solve();
}
#ifdef memset0
static void wrongAnswer(std::string message) {
printf("WA: %s\n", message.c_str());
exit(0);
}
namespace tree_helper {
static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;
static void dfs(
const std::vector<std::vector<int>>& adj_list,
int current_node, int parent_node) {
parent[0][current_node] = parent_node;
subtree_size[current_node] = 1;
for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
const int next_node = adj_list[current_node][i];
if (next_node != parent_node) {
depth[next_node] = depth[current_node] + 1;
dfs(adj_list, next_node, current_node);
subtree_size[current_node] += subtree_size[next_node];
}
}
}
static void initializeTree(const std::vector<std::vector<int>>& adj_list) {
N = static_cast<int>(adj_list.size());
depth = std::vector<int>(N, 0);
subtree_size = std::vector<int>(N, 0);
for (logN = 0; (1 << logN) < N; ++logN) {}
parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));
dfs(adj_list, 0, 0);
for (int i = 1; i < logN; ++i) {
for (int j = 0; j < N; ++j) {
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
static int getLowestCommonAncestor(int X, int Y) {
if (depth[X] < depth[Y]) {
std::swap(X, Y);
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] >= depth[Y]) {
X = parent[i][X];
}
}
if (X == Y) {
return X;
}
for (int i = logN - 1; i >= 0; --i) {
if (parent[i][X] != parent[i][Y]) {
X = parent[i][X];
Y = parent[i][Y];
}
}
return parent[0][X];
}
static int getDistance(int X, int Y) {
return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}
static int attractionsBehind(int X, int Y) {
if (X == Y) {
return N;
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] > depth[Y]) {
X = parent[i][X];
}
}
if (Y == parent[0][X]) {
return N - subtree_size[X];
}
return subtree_size[Y];
}
static void checkFunTour(const std::vector<int>& fun_tour) {
if (static_cast<int>(fun_tour.size()) != N) {
wrongAnswer("Invalid size");
}
std::vector<bool> visited_attractions(N, false);
for (int i = 0; i < N; ++i) {
if (fun_tour[i] < 0 || fun_tour[i] >= N) {
wrongAnswer("Invalid index");
}
if (visited_attractions[fun_tour[i]]) {
wrongAnswer("Repeated index");
}
visited_attractions[fun_tour[i]] = true;
}
int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
for (int i = 2; i < N; ++i) {
int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
if (travel_time > last_travel_time) {
wrongAnswer("Tour is not fun");
}
last_travel_time = travel_time;
}
}
} // namespace tree_helper
static int N, Q;
int hoursRequired(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::getDistance(X, Y);
}
int attractionsBehind(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::attractionsBehind(X, Y);
}
int main() {
#ifdef local
freopen("../examples/03.in", "r", stdin);
#endif
assert(2 == scanf("%d %d", &N, &Q));
std::vector<std::vector<int>> adj_list(N);
for (int i = 0; i < N - 1; ++i) {
int A, B;
assert(2 == scanf("%d %d", &A, &B));
adj_list[A].push_back(B);
adj_list[B].push_back(A);
}
tree_helper::initializeTree(adj_list);
std::vector<int> fun_tour = createFunTour(N, Q);
tree_helper::checkFunTour(fun_tour);
for (int i = 0; i < N; ++i) {
printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
}
return 0;
}
#endif
Compilation message
fun.cpp: In function 'std::vector<int> Task0::solve(int)':
fun.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int fl=0;fl<G.size();fl++){
| ~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
10 ms |
2772 KB |
Output is correct |
7 |
Correct |
23 ms |
5436 KB |
Output is correct |
8 |
Correct |
53 ms |
10552 KB |
Output is correct |
9 |
Correct |
109 ms |
20812 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
112 ms |
20812 KB |
Output is correct |
13 |
Correct |
93 ms |
20784 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
104 ms |
20768 KB |
Output is correct |
16 |
Correct |
110 ms |
20820 KB |
Output is correct |
17 |
Correct |
12 ms |
2884 KB |
Output is correct |
18 |
Correct |
27 ms |
5420 KB |
Output is correct |
19 |
Correct |
52 ms |
10572 KB |
Output is correct |
20 |
Correct |
120 ms |
20824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
10 ms |
2772 KB |
Output is correct |
7 |
Correct |
23 ms |
5436 KB |
Output is correct |
8 |
Correct |
53 ms |
10552 KB |
Output is correct |
9 |
Correct |
109 ms |
20812 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
112 ms |
20812 KB |
Output is correct |
13 |
Correct |
93 ms |
20784 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
104 ms |
20768 KB |
Output is correct |
16 |
Correct |
110 ms |
20820 KB |
Output is correct |
17 |
Correct |
12 ms |
2884 KB |
Output is correct |
18 |
Correct |
27 ms |
5420 KB |
Output is correct |
19 |
Correct |
52 ms |
10572 KB |
Output is correct |
20 |
Correct |
120 ms |
20824 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
304 KB |
Output is correct |
23 |
Correct |
1 ms |
308 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
312 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
300 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
308 KB |
Output is correct |
32 |
Correct |
1 ms |
308 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
2 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
216 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
2772 KB |
Output is correct |
6 |
Correct |
23 ms |
5436 KB |
Output is correct |
7 |
Correct |
53 ms |
10552 KB |
Output is correct |
8 |
Correct |
109 ms |
20812 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
308 KB |
Output is correct |
17 |
Correct |
2 ms |
304 KB |
Output is correct |
18 |
Correct |
135 ms |
18244 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
576 KB |
Output is correct |
21 |
Correct |
3 ms |
712 KB |
Output is correct |
22 |
Correct |
8 ms |
1364 KB |
Output is correct |
23 |
Correct |
17 ms |
2552 KB |
Output is correct |
24 |
Correct |
19 ms |
3480 KB |
Output is correct |
25 |
Correct |
84 ms |
10500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
216 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
112 ms |
20812 KB |
Output is correct |
6 |
Correct |
93 ms |
20784 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
14 ms |
1996 KB |
Output is correct |
15 |
Correct |
135 ms |
18252 KB |
Output is correct |
16 |
Correct |
177 ms |
18092 KB |
Output is correct |
17 |
Correct |
40 ms |
4496 KB |
Output is correct |
18 |
Correct |
78 ms |
8348 KB |
Output is correct |
19 |
Correct |
118 ms |
14324 KB |
Output is correct |
20 |
Correct |
8 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
10 ms |
2772 KB |
Output is correct |
7 |
Correct |
23 ms |
5436 KB |
Output is correct |
8 |
Correct |
53 ms |
10552 KB |
Output is correct |
9 |
Correct |
109 ms |
20812 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
112 ms |
20812 KB |
Output is correct |
13 |
Correct |
93 ms |
20784 KB |
Output is correct |
14 |
Correct |
1 ms |
312 KB |
Output is correct |
15 |
Correct |
104 ms |
20768 KB |
Output is correct |
16 |
Correct |
110 ms |
20820 KB |
Output is correct |
17 |
Correct |
12 ms |
2884 KB |
Output is correct |
18 |
Correct |
27 ms |
5420 KB |
Output is correct |
19 |
Correct |
52 ms |
10572 KB |
Output is correct |
20 |
Correct |
120 ms |
20824 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
304 KB |
Output is correct |
23 |
Correct |
1 ms |
308 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
312 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
300 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
308 KB |
Output is correct |
32 |
Correct |
1 ms |
308 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
2 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
308 KB |
Output is correct |
43 |
Correct |
2 ms |
304 KB |
Output is correct |
44 |
Correct |
135 ms |
18244 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
2 ms |
576 KB |
Output is correct |
47 |
Correct |
3 ms |
712 KB |
Output is correct |
48 |
Correct |
8 ms |
1364 KB |
Output is correct |
49 |
Correct |
17 ms |
2552 KB |
Output is correct |
50 |
Correct |
19 ms |
3480 KB |
Output is correct |
51 |
Correct |
84 ms |
10500 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
14 ms |
1996 KB |
Output is correct |
54 |
Correct |
135 ms |
18252 KB |
Output is correct |
55 |
Correct |
177 ms |
18092 KB |
Output is correct |
56 |
Correct |
40 ms |
4496 KB |
Output is correct |
57 |
Correct |
78 ms |
8348 KB |
Output is correct |
58 |
Correct |
118 ms |
14324 KB |
Output is correct |
59 |
Correct |
8 ms |
852 KB |
Output is correct |
60 |
Correct |
197 ms |
18240 KB |
Output is correct |
61 |
Correct |
245 ms |
20652 KB |
Output is correct |
62 |
Correct |
194 ms |
18672 KB |
Output is correct |
63 |
Correct |
278 ms |
22160 KB |
Output is correct |
64 |
Correct |
277 ms |
22188 KB |
Output is correct |
65 |
Correct |
218 ms |
18384 KB |
Output is correct |
66 |
Correct |
326 ms |
20660 KB |
Output is correct |
67 |
Correct |
270 ms |
22316 KB |
Output is correct |
68 |
Correct |
305 ms |
21640 KB |
Output is correct |
69 |
Correct |
409 ms |
22892 KB |
Output is correct |
70 |
Correct |
187 ms |
18380 KB |
Output is correct |
71 |
Correct |
254 ms |
22292 KB |
Output is correct |
72 |
Correct |
247 ms |
20948 KB |
Output is correct |
73 |
Correct |
210 ms |
21684 KB |
Output is correct |
74 |
Correct |
386 ms |
23228 KB |
Output is correct |
75 |
Correct |
204 ms |
18720 KB |
Output is correct |
76 |
Correct |
228 ms |
22232 KB |
Output is correct |
77 |
Correct |
231 ms |
22420 KB |
Output is correct |
78 |
Correct |
210 ms |
21784 KB |
Output is correct |
79 |
Correct |
367 ms |
22900 KB |
Output is correct |
80 |
Correct |
249 ms |
23232 KB |
Output is correct |
81 |
Correct |
181 ms |
18240 KB |
Output is correct |
82 |
Correct |
207 ms |
18248 KB |
Output is correct |
83 |
Correct |
203 ms |
18316 KB |
Output is correct |
84 |
Correct |
68 ms |
7804 KB |
Output is correct |