# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
925818 |
2024-02-12T09:21:11 Z |
adhityamv |
Fun Tour (APIO20_fun) |
C++17 |
|
176 ms |
21448 KB |
#include <bits/stdc++.h>
#include <fun.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
int n;
vector<int> dist;
int get_centroid(){
int ind=0,val=n;
for(int i=1;i<n;i++){
int num=attractionsBehind(0,i);
if(num>=(n+1)/2){
if(ind==-1 || val>num){
ind=i;
val=num;
}
}
}
return ind;
}
vector<int> deg2(int c,int x,int y){
vector<pii> part1;
vector<pii> part2;
for(int i=0;i<n;i++){
if(i==c) continue;
if(attractionsBehind(i,x)>n/2){
part1.push_back(mp(dist[i],i));
} else part2.push_back(mp(dist[i],i));
}
if(part1.size()<=part2.size()) part1.push_back(mp(0,c));
else part2.push_back(mp(0,c));
sort(part1.begin(),part1.end());
sort(part2.begin(),part2.end());
int ind1=part1.size()-1;
int ind2=part2.size()-1;
vector<int> ans;
for(int i=0;i<n;i++){
if(i%2==0){
ans.push_back(part1[ind1].se);
ind1--;
} else{
ans.push_back(part2[ind2].se);
ind2--;
}
}
return ans;
}
vector<int> deg3(int c,int x,int y,int z){
vector<int> ans;
vector<pii> part[3];
for(int i=0;i<n;i++){
if(i==c) continue;
if(attractionsBehind(i,x)>n/2){
part[0].push_back(mp(dist[i],i));
} else if(attractionsBehind(i,y)>n/2){
part[1].push_back(mp(dist[i],i));
} else part[2].push_back(mp(dist[i],i));
}
int siz[3];
for(int i=0;i<3;i++) siz[i]=part[i].size();
int mnind=0;
for(int i=1;i<3;i++) if(siz[i]<siz[mnind]) mnind=i;
part[mnind].push_back(mp(0,c));
siz[mnind]++;
for(int i=0;i<3;i++) sort(part[i].begin(),part[i].end());
int prev=-1;
while(siz[0]!=siz[1]+siz[2] && siz[1]!=siz[2]+siz[0] && siz[2]!=siz[0]+siz[1]){
int mx=0;
int ind;
for(int i=0;i<3;i++){
if(i==prev) continue;
if(part[i][siz[i]-1].fi>mx){
mx=part[i][siz[i]-1].fi;
ind=i;
}
}
ans.push_back(part[ind][siz[ind]-1].se);
siz[ind]--;
prev=ind;
}
for(int i=0;i<3;i++){
if(2*siz[i]==siz[0]+siz[1]+siz[2]){
vector<pii> u,v;
for(int j=0;j<siz[i];j++) u.push_back(part[i][j]);
for(int k=0;k<3;k++){
if(k==i) continue;
for(int j=0;j<siz[k];j++) v.push_back(part[k][j]);
}
sort(u.begin(),u.end());
sort(v.begin(),v.end());
bool swu=true;
if(prev==i || prev==-1) swu=false;
else{
for(int j=0;j<3;j++){
if(j==prev) continue;
if(j==i) continue;
if(part[j][siz[j]-1].fi>part[prev][siz[prev]].fi) swu=false;
}
}
for(int j=siz[i]-1;j>=0;j--){
if(!swu){
ans.push_back(v[j].se);
ans.push_back(u[j].se);
} else{
ans.push_back(u[j].se);
ans.push_back(v[j].se);
}
}
return ans;
}
}
}
vector<int> createFunTour(int nn, int q){
n=nn;
int c=get_centroid();
for(int i=0;i<n;i++){
if(i==c) dist.push_back(0);
else dist.push_back(hoursRequired(c,i));
}
int cnt=0;
vector<int> roots;
for(int i=0;i<n;i++) if(dist[i]==1){
cnt++;
roots.push_back(i);
}
if(cnt==1) return {0,1};
if(cnt==2) return deg2(c,roots[0],roots[1]);
else return deg3(c,roots[0],roots[1],roots[2]);
}
Compilation message
fun.cpp: In function 'std::vector<int> deg3(int, int, int, int)':
fun.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
115 | }
| ^
fun.cpp:81:17: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | siz[ind]--;
| ~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
600 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
86 ms |
15560 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
860 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
9 ms |
2192 KB |
Output is correct |
24 |
Correct |
11 ms |
2904 KB |
Output is correct |
25 |
Correct |
54 ms |
9112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
7 ms |
1700 KB |
Output is correct |
15 |
Correct |
91 ms |
15288 KB |
Output is correct |
16 |
Correct |
96 ms |
15080 KB |
Output is correct |
17 |
Correct |
16 ms |
3928 KB |
Output is correct |
18 |
Correct |
39 ms |
7092 KB |
Output is correct |
19 |
Correct |
69 ms |
12012 KB |
Output is correct |
20 |
Correct |
3 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
600 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
348 KB |
Output is correct |
44 |
Correct |
86 ms |
15560 KB |
Output is correct |
45 |
Correct |
1 ms |
344 KB |
Output is correct |
46 |
Correct |
2 ms |
604 KB |
Output is correct |
47 |
Correct |
2 ms |
860 KB |
Output is correct |
48 |
Correct |
4 ms |
1372 KB |
Output is correct |
49 |
Correct |
9 ms |
2192 KB |
Output is correct |
50 |
Correct |
11 ms |
2904 KB |
Output is correct |
51 |
Correct |
54 ms |
9112 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
7 ms |
1700 KB |
Output is correct |
54 |
Correct |
91 ms |
15288 KB |
Output is correct |
55 |
Correct |
96 ms |
15080 KB |
Output is correct |
56 |
Correct |
16 ms |
3928 KB |
Output is correct |
57 |
Correct |
39 ms |
7092 KB |
Output is correct |
58 |
Correct |
69 ms |
12012 KB |
Output is correct |
59 |
Correct |
3 ms |
860 KB |
Output is correct |
60 |
Correct |
114 ms |
16516 KB |
Output is correct |
61 |
Correct |
126 ms |
18992 KB |
Output is correct |
62 |
Correct |
122 ms |
17096 KB |
Output is correct |
63 |
Correct |
117 ms |
20424 KB |
Output is correct |
64 |
Correct |
120 ms |
20400 KB |
Output is correct |
65 |
Correct |
125 ms |
16680 KB |
Output is correct |
66 |
Correct |
139 ms |
18940 KB |
Output is correct |
67 |
Correct |
132 ms |
21348 KB |
Output is correct |
68 |
Correct |
151 ms |
20664 KB |
Output is correct |
69 |
Correct |
176 ms |
21108 KB |
Output is correct |
70 |
Correct |
110 ms |
16844 KB |
Output is correct |
71 |
Correct |
120 ms |
20428 KB |
Output is correct |
72 |
Correct |
130 ms |
19152 KB |
Output is correct |
73 |
Correct |
141 ms |
20620 KB |
Output is correct |
74 |
Correct |
153 ms |
21448 KB |
Output is correct |
75 |
Correct |
124 ms |
17624 KB |
Output is correct |
76 |
Correct |
119 ms |
20632 KB |
Output is correct |
77 |
Correct |
136 ms |
21240 KB |
Output is correct |
78 |
Correct |
124 ms |
20752 KB |
Output is correct |
79 |
Correct |
158 ms |
21128 KB |
Output is correct |
80 |
Correct |
160 ms |
21448 KB |
Output is correct |
81 |
Correct |
120 ms |
16556 KB |
Output is correct |
82 |
Correct |
115 ms |
16844 KB |
Output is correct |
83 |
Correct |
123 ms |
16616 KB |
Output is correct |
84 |
Correct |
49 ms |
7184 KB |
Output is correct |