#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)
typedef pair<int,int>pi;
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//----------------------
const int MX=1e5+10;
int N;
int C;
void find_centroid(){
vi sub(N);
FOR(i,0,N) sub[i]=attractionsBehind(0,i);
C=-1;
FOR(i,0,N) if(sub[i]>=(N+1)/2){
if(C==-1) C=i;
else if(sub[i]<sub[C]) C=i;
}
}
vi distC(MX);
vector<vi>subb;
vector<set<pi,greater<pi>>>sub;
void divide(){
FOR(i,0,N) distC[i]=hoursRequired(C,i);
FOR(i,0,N) if(distC[i]==1) subb.pb(vi{i});
assert(sz(subb)>=2);
vi vis(N,0);
FOR(i,0,2){
int c=subb[i][0];
vi dist(N);
FOR(j,0,N) dist[j]=hoursRequired(c,j);
FOR(j,0,N) if(j!=c && dist[j]==distC[j]-1) subb[i].pb(j);
for(int x: subb[i]) vis[x]=1;
}
vis[C]=1; if(sz(subb)>2) vis[subb[2][0]]=1;
FOR(i,0,N) if(!vis[i]) subb[2].pb(i);
FOR(i,0,sz(subb)){
set<pi,greater<pi>>s;
for(int u: subb[i]) s.insert({distC[u],u});
sub.pb(s);
}
}
vi ans;
void solve(){
int nb=sz(subb);
int u=C;
FOR(j,0,nb){
for(int i: subb[j]) if(distC[i]>distC[u]) u=i;
}
int merged=0;
while(1){
//merge if possible
for(int i=0; i<nb && !merged; i++){
int x=0;
FOR(j,0,nb) if(i!=j) x+=sz(sub[j]);
if(x<=sz(sub[i])){
int j=0; if(i==0) j++;
FOR(k,0,nb) if(k!=i && k!=j){
for(auto x: sub[k]) sub[j].insert(x);
sub[k].clear();
}
merged=1;
//careful
int prev=-1;
if(sz(ans)) prev=ans.back();
if(prev==-1) u=(*sub[i].begin()).se;
else{
if(distC[prev]>distC[u]) u=(*sub[i].begin()).se;
}
}
}
//erase the current one & move to the next
ans.pb(u);
int idx;
FOR(i,0,nb) if(sub[i].count({distC[u],u}))
sub[i].erase({distC[u],u}),idx=i;
int nxt=-1;
FOR(i,0,nb) if(i!=idx && sz(sub[i])){
int v=(*sub[i].begin()).se;
if(nxt==-1) nxt=v;
else if(distC[v]>distC[nxt]) nxt=v;
}
if(nxt==-1) break;
u=nxt;
}
ans.pb(C);
}
vi createFunTour(int N, int Q){
if(N==2) return vi{0,1};
::N=N;
find_centroid();
divide();
solve();
return ans;
}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/
Compilation message
fun.cpp: In function 'void solve()':
fun.cpp:107:31: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
107 | FOR(i,0,nb) if(i!=idx && sz(sub[i])){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
700 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
588 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
588 KB |
Output is correct |
17 |
Correct |
1 ms |
588 KB |
Output is correct |
18 |
Correct |
1 ms |
588 KB |
Output is correct |
19 |
Correct |
1 ms |
588 KB |
Output is correct |
20 |
Correct |
1 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
700 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
588 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
588 KB |
Output is correct |
17 |
Correct |
1 ms |
588 KB |
Output is correct |
18 |
Correct |
1 ms |
588 KB |
Output is correct |
19 |
Correct |
1 ms |
588 KB |
Output is correct |
20 |
Correct |
1 ms |
588 KB |
Output is correct |
21 |
Correct |
1 ms |
588 KB |
Output is correct |
22 |
Correct |
1 ms |
588 KB |
Output is correct |
23 |
Correct |
1 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
1 ms |
588 KB |
Output is correct |
26 |
Correct |
1 ms |
716 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
0 ms |
588 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
2 ms |
696 KB |
Output is correct |
31 |
Correct |
1 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
716 KB |
Output is correct |
33 |
Correct |
1 ms |
704 KB |
Output is correct |
34 |
Correct |
1 ms |
716 KB |
Output is correct |
35 |
Correct |
2 ms |
696 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
1 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
716 KB |
Output is correct |
39 |
Correct |
0 ms |
716 KB |
Output is correct |
40 |
Correct |
1 ms |
716 KB |
Output is correct |
41 |
Correct |
1 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
2 ms |
716 KB |
Output is correct |
13 |
Correct |
1 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
716 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
2 ms |
716 KB |
Output is correct |
17 |
Correct |
1 ms |
716 KB |
Output is correct |
18 |
Correct |
192 ms |
20784 KB |
Output is correct |
19 |
Correct |
2 ms |
844 KB |
Output is correct |
20 |
Correct |
3 ms |
972 KB |
Output is correct |
21 |
Correct |
5 ms |
1228 KB |
Output is correct |
22 |
Correct |
10 ms |
1996 KB |
Output is correct |
23 |
Correct |
24 ms |
3392 KB |
Output is correct |
24 |
Correct |
27 ms |
4264 KB |
Output is correct |
25 |
Correct |
109 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
700 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
0 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
696 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
1 ms |
716 KB |
Output is correct |
12 |
Correct |
1 ms |
704 KB |
Output is correct |
13 |
Correct |
3 ms |
844 KB |
Output is correct |
14 |
Correct |
15 ms |
2764 KB |
Output is correct |
15 |
Correct |
223 ms |
21820 KB |
Output is correct |
16 |
Correct |
224 ms |
22276 KB |
Output is correct |
17 |
Correct |
37 ms |
5700 KB |
Output is correct |
18 |
Correct |
89 ms |
10264 KB |
Output is correct |
19 |
Correct |
162 ms |
16916 KB |
Output is correct |
20 |
Correct |
7 ms |
1484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
700 KB |
Output is correct |
12 |
Correct |
1 ms |
588 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
588 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
588 KB |
Output is correct |
17 |
Correct |
1 ms |
588 KB |
Output is correct |
18 |
Correct |
1 ms |
588 KB |
Output is correct |
19 |
Correct |
1 ms |
588 KB |
Output is correct |
20 |
Correct |
1 ms |
588 KB |
Output is correct |
21 |
Correct |
1 ms |
588 KB |
Output is correct |
22 |
Correct |
1 ms |
588 KB |
Output is correct |
23 |
Correct |
1 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
1 ms |
588 KB |
Output is correct |
26 |
Correct |
1 ms |
716 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
0 ms |
588 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
2 ms |
696 KB |
Output is correct |
31 |
Correct |
1 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
716 KB |
Output is correct |
33 |
Correct |
1 ms |
704 KB |
Output is correct |
34 |
Correct |
1 ms |
716 KB |
Output is correct |
35 |
Correct |
2 ms |
696 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
1 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
716 KB |
Output is correct |
39 |
Correct |
0 ms |
716 KB |
Output is correct |
40 |
Correct |
1 ms |
716 KB |
Output is correct |
41 |
Correct |
1 ms |
692 KB |
Output is correct |
42 |
Correct |
2 ms |
716 KB |
Output is correct |
43 |
Correct |
1 ms |
716 KB |
Output is correct |
44 |
Correct |
192 ms |
20784 KB |
Output is correct |
45 |
Correct |
2 ms |
844 KB |
Output is correct |
46 |
Correct |
3 ms |
972 KB |
Output is correct |
47 |
Correct |
5 ms |
1228 KB |
Output is correct |
48 |
Correct |
10 ms |
1996 KB |
Output is correct |
49 |
Correct |
24 ms |
3392 KB |
Output is correct |
50 |
Correct |
27 ms |
4264 KB |
Output is correct |
51 |
Correct |
109 ms |
12636 KB |
Output is correct |
52 |
Correct |
3 ms |
844 KB |
Output is correct |
53 |
Correct |
15 ms |
2764 KB |
Output is correct |
54 |
Correct |
223 ms |
21820 KB |
Output is correct |
55 |
Correct |
224 ms |
22276 KB |
Output is correct |
56 |
Correct |
37 ms |
5700 KB |
Output is correct |
57 |
Correct |
89 ms |
10264 KB |
Output is correct |
58 |
Correct |
162 ms |
16916 KB |
Output is correct |
59 |
Correct |
7 ms |
1484 KB |
Output is correct |
60 |
Correct |
263 ms |
22608 KB |
Output is correct |
61 |
Correct |
340 ms |
25072 KB |
Output is correct |
62 |
Correct |
274 ms |
22588 KB |
Output is correct |
63 |
Correct |
303 ms |
26496 KB |
Output is correct |
64 |
Correct |
412 ms |
26556 KB |
Output is correct |
65 |
Correct |
285 ms |
22616 KB |
Output is correct |
66 |
Correct |
469 ms |
25028 KB |
Output is correct |
67 |
Correct |
331 ms |
26500 KB |
Output is correct |
68 |
Correct |
368 ms |
25924 KB |
Output is correct |
69 |
Correct |
437 ms |
26808 KB |
Output is correct |
70 |
Correct |
287 ms |
21456 KB |
Output is correct |
71 |
Correct |
312 ms |
25384 KB |
Output is correct |
72 |
Correct |
374 ms |
25144 KB |
Output is correct |
73 |
Correct |
309 ms |
25788 KB |
Output is correct |
74 |
Correct |
466 ms |
26956 KB |
Output is correct |
75 |
Correct |
270 ms |
21428 KB |
Output is correct |
76 |
Correct |
371 ms |
26396 KB |
Output is correct |
77 |
Correct |
368 ms |
26624 KB |
Output is correct |
78 |
Correct |
328 ms |
24764 KB |
Output is correct |
79 |
Correct |
419 ms |
27168 KB |
Output is correct |
80 |
Correct |
412 ms |
27416 KB |
Output is correct |
81 |
Correct |
269 ms |
21712 KB |
Output is correct |
82 |
Correct |
311 ms |
21692 KB |
Output is correct |
83 |
Correct |
418 ms |
21820 KB |
Output is correct |
84 |
Correct |
117 ms |
9628 KB |
Output is correct |