# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
292330 |
2020-09-06T20:42:52 Z |
Lawliet |
Fun Tour (APIO20_fun) |
C++17 |
|
414 ms |
20024 KB |
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int n;
int depth[MAXN];
vector<int> adj;
vector<int> groups[5];
bool cmp(int i, int j) { return depth[i] < depth[j]; }
bool hasMajoritary()
{
int mx = 0;
int sum = 0;
for(int i = 0 ; i < 3 ; i++)
{
sum += (int)groups[i].size();
mx = max( mx , (int)groups[i].size() );
}
return ( sum - mx <= mx );
}
int getCentroid()
{
int sub = n;
int cent = 0;
for(int i = 1 ; i < n ; i++)
{
int curSub = attractionsBehind( 0 , i );
if( curSub > n/2 && curSub < sub )
{
cent = i;
sub = curSub;
}
}
return cent;
}
void findGroups()
{
int degree = 0;
for(int i = 0 ; i < n ; i++)
{
if( depth[i] == 1 )
{
adj.push_back( i );
groups[degree++].push_back( i );
}
}
for(int i = 0 ; i < n ; i++)
{
if( depth[i] <= 1 ) continue;
int distA = hoursRequired( i , adj[0] );
int distB = hoursRequired( i , adj[1] );
if( distA < distB ) groups[0].push_back( i );
if( distA > distB ) groups[1].push_back( i );
if( distA == distB ) groups[2].push_back( i );
}
for(int i = 0 ; i < degree ; i++)
sort( groups[i].begin() , groups[i].end() , cmp );
}
int getMajoritary()
{
int maj = 0;
for(int i = 0 ; i < 3 ; i++)
if( (int)groups[maj].size() <= (int)groups[i].size() ) maj = i;
return maj;
}
vector<int> createFunTour(int N, int Q)
{
n = N;
if( N == 2 )
{
vector<int> ans = { 0 , 1 };
return ans;
}
int cent = getCentroid();
depth[cent] = 0;
for(int i = 0 ; i < N ; i++)
if( i != cent ) depth[i] = hoursRequired( cent , i );
findGroups();
int first = 0;
vector<int> ans;
int last = -1;
while( !hasMajoritary() )
{
int nxt = 0;
if( last == 0 ) nxt = 1;
for(int i = 0 ; i < 3 ; i++)
{
if( last == i ) continue;
if( depth[ groups[nxt].back() ] <= depth[ groups[i].back() ] )
nxt = i;
}
last = nxt;
ans.push_back( groups[nxt].back() );
groups[nxt].pop_back();
}
int indMajoritary = getMajoritary();
if( last != -1 )
{
int otherGroup = 3 - last - indMajoritary;
if( depth[ ans.back() ] <= depth[ groups[otherGroup].back() ] )
first = 1;
}
if( indMajoritary != 0 )
swap( groups[0] , groups[indMajoritary] );
while( !groups[2].empty() )
{
groups[1].push_back( groups[2].back() );
groups[2].pop_back();
}
sort( groups[1].begin() , groups[1].end() , cmp );
for(int i = 1 ; i <= 3*N ; i++)
{
if( !groups[first].empty() )
{
ans.push_back( groups[first].back() );
groups[first].pop_back();
}
if( !groups[1 - first].empty() )
{
ans.push_back( groups[1 - first].back() );
groups[1 - first].pop_back();
}
}
ans.push_back( cent );
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
0 ms |
256 KB |
Output is correct |
23 |
Correct |
0 ms |
256 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
0 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
0 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
0 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
150 ms |
14960 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
4 ms |
708 KB |
Output is correct |
22 |
Correct |
7 ms |
1280 KB |
Output is correct |
23 |
Correct |
14 ms |
2176 KB |
Output is correct |
24 |
Correct |
19 ms |
2944 KB |
Output is correct |
25 |
Correct |
83 ms |
8720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
11 ms |
1664 KB |
Output is correct |
15 |
Correct |
166 ms |
14960 KB |
Output is correct |
16 |
Correct |
167 ms |
14836 KB |
Output is correct |
17 |
Correct |
28 ms |
3712 KB |
Output is correct |
18 |
Correct |
74 ms |
6976 KB |
Output is correct |
19 |
Correct |
128 ms |
11848 KB |
Output is correct |
20 |
Correct |
5 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
0 ms |
256 KB |
Output is correct |
23 |
Correct |
0 ms |
256 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
0 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
0 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
0 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
384 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
1 ms |
384 KB |
Output is correct |
44 |
Correct |
150 ms |
14960 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
2 ms |
512 KB |
Output is correct |
47 |
Correct |
4 ms |
708 KB |
Output is correct |
48 |
Correct |
7 ms |
1280 KB |
Output is correct |
49 |
Correct |
14 ms |
2176 KB |
Output is correct |
50 |
Correct |
19 ms |
2944 KB |
Output is correct |
51 |
Correct |
83 ms |
8720 KB |
Output is correct |
52 |
Correct |
1 ms |
384 KB |
Output is correct |
53 |
Correct |
11 ms |
1664 KB |
Output is correct |
54 |
Correct |
166 ms |
14960 KB |
Output is correct |
55 |
Correct |
167 ms |
14836 KB |
Output is correct |
56 |
Correct |
28 ms |
3712 KB |
Output is correct |
57 |
Correct |
74 ms |
6976 KB |
Output is correct |
58 |
Correct |
128 ms |
11848 KB |
Output is correct |
59 |
Correct |
5 ms |
896 KB |
Output is correct |
60 |
Correct |
228 ms |
15216 KB |
Output is correct |
61 |
Correct |
286 ms |
17624 KB |
Output is correct |
62 |
Correct |
217 ms |
15216 KB |
Output is correct |
63 |
Correct |
261 ms |
19184 KB |
Output is correct |
64 |
Correct |
260 ms |
19184 KB |
Output is correct |
65 |
Correct |
252 ms |
15216 KB |
Output is correct |
66 |
Correct |
297 ms |
17392 KB |
Output is correct |
67 |
Correct |
269 ms |
19312 KB |
Output is correct |
68 |
Correct |
279 ms |
18416 KB |
Output is correct |
69 |
Correct |
405 ms |
20024 KB |
Output is correct |
70 |
Correct |
222 ms |
15088 KB |
Output is correct |
71 |
Correct |
280 ms |
18928 KB |
Output is correct |
72 |
Correct |
316 ms |
17640 KB |
Output is correct |
73 |
Correct |
290 ms |
18544 KB |
Output is correct |
74 |
Correct |
385 ms |
19824 KB |
Output is correct |
75 |
Correct |
234 ms |
15172 KB |
Output is correct |
76 |
Correct |
276 ms |
19056 KB |
Output is correct |
77 |
Correct |
290 ms |
19076 KB |
Output is correct |
78 |
Correct |
304 ms |
18288 KB |
Output is correct |
79 |
Correct |
379 ms |
19952 KB |
Output is correct |
80 |
Correct |
414 ms |
19952 KB |
Output is correct |
81 |
Correct |
238 ms |
14960 KB |
Output is correct |
82 |
Correct |
259 ms |
14960 KB |
Output is correct |
83 |
Correct |
264 ms |
15272 KB |
Output is correct |
84 |
Correct |
89 ms |
6560 KB |
Output is correct |