# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
434907 |
2021-06-22T06:42:53 Z |
dqhungdl |
Fun Tour (APIO20_fun) |
C++17 |
|
376 ms |
21392 KB |
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
bool cmp(vector<ii> g1,vector<ii> g2) {
return g1.size()>g2.size();
}
vector<ii> merge(vector<ii> g1,vector<ii> g2) {
while(g2.size()>0) {
g1.push_back(g2.back());
g2.pop_back();
}
sort(g1.begin(),g1.end());
return g1;
}
int getBack(vector<ii> &V) {
if(V.size()==0)
return -1;
return V.back().first;
}
std::vector<int> createFunTour(int N, int Q) {
// Special case
if(N==2)
return {0,1};
// Find centroid
int R=0,minVal=1e9;
for(int i=1;i<N;i++) {
int subtree=attractionsBehind(R,i)-1;
if(subtree>=N/2&&minVal>subtree) {
minVal=subtree;
R=i;
}
}
// Find distance and adjacents from centroid R
vector<int> adj,dist(N);
for(int i=0;i<N;i++) {
dist[i]=hoursRequired(R,i);
if(dist[i]==1)
adj.push_back(i);
}
// Divide into parts
vector<ii> g[adj.size()];
for(int i=0;i<N;i++) {
if(i==R)
continue;
bool valid=false;
for(int j=0;j<adj.size();j++)
if(adj[j]==i) {
g[j].push_back({1,i});
valid=true;
break;
}
if(valid)
continue;
for(int j=0;j<adj.size()-1;j++)
if(dist[i]==hoursRequired(i,adj[j])+1) {
g[j].push_back({dist[i],i});
valid=true;
break;
}
if(!valid)
g[adj.size()-1].push_back({dist[i],i});
}
// Sort sets
sort(g,g+adj.size(),cmp);
g[adj.size()-1].push_back({0,R});
for(int i=0;i<adj.size();i++)
sort(g[i].begin(),g[i].end());
// Generate path
vector<int> rs;
int turn=0;
if(adj.size()==3) {
int pre=-1;
while(g[0].size()>0||g[1].size()>0||g[2].size()>0) {
if(g[0].size()+g[1].size()==g[2].size()) {
g[0]=merge(g[0],g[1]);
g[1]=g[2];
turn=(pre==0||pre==1?1:0);
break;
} else if(g[0].size()+g[2].size()==g[1].size()) {
g[0]=merge(g[0],g[2]);
turn=(pre==0||pre==2?1:0);
break;
} else if(g[1].size()+g[2].size()==g[0].size()) {
g[1]=merge(g[1],g[2]);
turn=(pre==0?1:0);
break;
}
int newPre=-1;
for(int i=0;i<adj.size();i++) {
if(i==pre||g[i].size()==0)
continue;
if(newPre==-1||g[newPre].back()<g[i].back())
newPre=i;
}
//assert(newPre!=-1);
pre=newPre;
rs.push_back(g[pre].back().second);
g[pre].pop_back();
}
if(g[turn^1].size()>0&&g[turn^1].back().first>g[turn].back().first
&&rs.size()>0&&hoursRequired(rs.back(),g[turn^1].back().second)==dist[rs.back()]+dist[g[turn^1].back().second])
turn^=1;
}
while(g[0].size()>0||g[1].size()>0) {
if(g[turn].size()==0)
turn^=1;
rs.push_back(g[turn].back().second);
g[turn].pop_back();
turn^=1;
}
return rs;
}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=0;j<adj.size();j++)
| ~^~~~~~~~~~~
fun.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int j=0;j<adj.size()-1;j++)
| ~^~~~~~~~~~~~~
fun.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<adj.size();i++)
| ~^~~~~~~~~~~
fun.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0;i<adj.size();i++) {
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
284 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
292 KB |
Output is correct |
31 |
Correct |
1 ms |
288 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
142 ms |
15540 KB |
Output is correct |
19 |
Correct |
1 ms |
392 KB |
Output is correct |
20 |
Correct |
2 ms |
460 KB |
Output is correct |
21 |
Correct |
4 ms |
612 KB |
Output is correct |
22 |
Correct |
7 ms |
1228 KB |
Output is correct |
23 |
Correct |
16 ms |
2240 KB |
Output is correct |
24 |
Correct |
19 ms |
2896 KB |
Output is correct |
25 |
Correct |
79 ms |
8984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
1 ms |
288 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
11 ms |
1612 KB |
Output is correct |
15 |
Correct |
143 ms |
15536 KB |
Output is correct |
16 |
Correct |
150 ms |
15128 KB |
Output is correct |
17 |
Correct |
36 ms |
3656 KB |
Output is correct |
18 |
Correct |
68 ms |
7216 KB |
Output is correct |
19 |
Correct |
115 ms |
11888 KB |
Output is correct |
20 |
Correct |
5 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
284 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
292 KB |
Output is correct |
31 |
Correct |
1 ms |
288 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
142 ms |
15540 KB |
Output is correct |
45 |
Correct |
1 ms |
392 KB |
Output is correct |
46 |
Correct |
2 ms |
460 KB |
Output is correct |
47 |
Correct |
4 ms |
612 KB |
Output is correct |
48 |
Correct |
7 ms |
1228 KB |
Output is correct |
49 |
Correct |
16 ms |
2240 KB |
Output is correct |
50 |
Correct |
19 ms |
2896 KB |
Output is correct |
51 |
Correct |
79 ms |
8984 KB |
Output is correct |
52 |
Correct |
2 ms |
332 KB |
Output is correct |
53 |
Correct |
11 ms |
1612 KB |
Output is correct |
54 |
Correct |
143 ms |
15536 KB |
Output is correct |
55 |
Correct |
150 ms |
15128 KB |
Output is correct |
56 |
Correct |
36 ms |
3656 KB |
Output is correct |
57 |
Correct |
68 ms |
7216 KB |
Output is correct |
58 |
Correct |
115 ms |
11888 KB |
Output is correct |
59 |
Correct |
5 ms |
716 KB |
Output is correct |
60 |
Correct |
210 ms |
15980 KB |
Output is correct |
61 |
Correct |
236 ms |
18492 KB |
Output is correct |
62 |
Correct |
244 ms |
16316 KB |
Output is correct |
63 |
Correct |
229 ms |
20256 KB |
Output is correct |
64 |
Correct |
219 ms |
19804 KB |
Output is correct |
65 |
Correct |
247 ms |
16236 KB |
Output is correct |
66 |
Correct |
248 ms |
18440 KB |
Output is correct |
67 |
Correct |
240 ms |
20020 KB |
Output is correct |
68 |
Correct |
281 ms |
19300 KB |
Output is correct |
69 |
Correct |
304 ms |
20820 KB |
Output is correct |
70 |
Correct |
191 ms |
16260 KB |
Output is correct |
71 |
Correct |
209 ms |
20260 KB |
Output is correct |
72 |
Correct |
254 ms |
18716 KB |
Output is correct |
73 |
Correct |
238 ms |
19172 KB |
Output is correct |
74 |
Correct |
294 ms |
20788 KB |
Output is correct |
75 |
Correct |
201 ms |
16316 KB |
Output is correct |
76 |
Correct |
232 ms |
20412 KB |
Output is correct |
77 |
Correct |
229 ms |
20160 KB |
Output is correct |
78 |
Correct |
241 ms |
19320 KB |
Output is correct |
79 |
Correct |
376 ms |
21192 KB |
Output is correct |
80 |
Correct |
301 ms |
21392 KB |
Output is correct |
81 |
Correct |
242 ms |
16700 KB |
Output is correct |
82 |
Correct |
200 ms |
16744 KB |
Output is correct |
83 |
Correct |
233 ms |
16456 KB |
Output is correct |
84 |
Correct |
77 ms |
7020 KB |
Output is correct |