# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
568821 |
2022-05-26T08:34:02 Z |
Zanite |
Fun Tour (APIO20_fun) |
C++17 |
|
134 ms |
16336 KB |
// You can't change other people; you can only change yourself.
#include "fun.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;
// Data types
using i8 = __int128;
using ll = long long;
using si = short int;
using ld = long double;
// Pairs
using pi8 = pair<i8, i8>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using psi = pair<si, si>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'
// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}
// Constants
const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
vector<int> createFunTour(int N, int Q) {
// corner case
if (N == 2) {return {0, 1};}
// Find centroid of tree
int minSubtree = iINF, centroid = -1;
int _0 = attractionsBehind(1, 0);
if (_0 >= (N+1)/2) {
minSubtree = _0;
centroid = 0;
}
for (int i = 1; i < N; i++) {
int cur = attractionsBehind(0, i);
if (cur >= (N+1)/2 && cur < minSubtree) {
centroid = i;
minSubtree = cur;
}
}
//printf("Centroid: %d\n", centroid);
// Find distance of all nodes to centroid
// Also find the 'groups' of nodes from centroid
vector<int> groupRep, groupRepSize;
vector<vector<pii>> groups;
vector<int> dist(N);
for (int i = 0; i < N; i++) {
if (i == centroid) continue;
dist[i] = hoursRequired(centroid, i);
if (dist[i] == 1) {
groupRep.push_back(i);
groups.push_back({{1, i}});
}
}
for (auto i : groupRep) {
groupRepSize.push_back(attractionsBehind(centroid, i));
}
assert(groupRep.size() > 1);
//for (auto i : dist) cout << i << ' '; cout << '\n';
//for (auto i : groupRep) cout << i << ' '; cout << '\n';
//for (auto i : groupRepSize) cout << i << ' '; cout << '\n';
// Find which group each node belongs to
for (int i = 0; i < N; i++) {
if (dist[i] <= 1) continue;
bool found = 0;
for (int g = 0; g < groupRep.size()-1; g++) {
//printf("Checking %d in group %d\n", i, groupRep[g]);
if (hoursRequired(i, groupRep[g]) == dist[i] - 1) {
groups[g].push_back({dist[i], i});
found = 1;
break;
}
}
if (!found) {
groups.back().push_back({dist[i], i});
}
}
for (auto &g : groups) {
sort(g.begin(), g.end());
//for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
}
// construct fun tour!
vector<int> ans;
int lastPicked = -1;
for (int i = 1; i < N; i++) {
//printf("Last picked %d\n", lastPicked);
//for (auto g : groups) {
// for (auto h : g) printf("{%d, %d} ", h.fi, h.se); cout << '\n';
//}
if (groups.size() == 3) {
int mx = -1, mxIndex = -1;
for (int g = 0; g < 3; g++) {
if (g == lastPicked) continue;
if (groups[g].back().fi > mx) {
mx = groups[g].back().fi;
mxIndex = g;
}
}
ans.push_back(groups[mxIndex].back().se);
groups[mxIndex].pop_back();
lastPicked = mxIndex;
int sz[] = {(int)groups[0].size(), (int)groups[1].size(), (int)groups[2].size()};
bool merge = 0;
if (sz[0] + sz[1] == sz[2]) {
merge = 1;
swap(groups[0], groups[2]);
if (lastPicked == 0) {lastPicked = 1;}
else if (lastPicked == 2) {lastPicked = 0;}
} else if (sz[0] + sz[2] == sz[1]) {
merge = 1;
swap(groups[0], groups[1]);
if (lastPicked == 2) {lastPicked = 1;}
else if (lastPicked == 1) {lastPicked = 0;}
} else if (sz[1] + sz[2] == sz[0]) {
merge = 1;
if (lastPicked == 2) {lastPicked = 1;}
}
if (merge) {
for (auto x : groups[2]) {groups[1].push_back(x);}
groups.pop_back();
sort(groups.back().begin(), groups.back().end());
}
} else {
for (int g = 0; g < 2; g++) {
if (lastPicked == g) {continue;}
ans.push_back(groups[g].back().se);
groups[g].pop_back();
lastPicked = g;
break;
}
}
}
ans.push_back(centroid);
//for (auto i : ans) {cout << i << ' ';} cout << '\n';
return ans;
}
//int main() {}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int g = 0; g < groupRep.size()-1; g++) {
| ~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
300 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
300 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 |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
296 KB |
Output is correct |
31 |
Correct |
1 ms |
300 KB |
Output is correct |
32 |
Correct |
1 ms |
300 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Incorrect |
1 ms |
300 KB |
Repeated index |
35 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
300 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 |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
296 KB |
Output is correct |
18 |
Correct |
105 ms |
15676 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
3 ms |
572 KB |
Output is correct |
21 |
Correct |
4 ms |
724 KB |
Output is correct |
22 |
Correct |
6 ms |
1236 KB |
Output is correct |
23 |
Correct |
11 ms |
2260 KB |
Output is correct |
24 |
Correct |
19 ms |
3028 KB |
Output is correct |
25 |
Correct |
67 ms |
9220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
9 ms |
1716 KB |
Output is correct |
15 |
Correct |
122 ms |
16336 KB |
Output is correct |
16 |
Correct |
134 ms |
16228 KB |
Output is correct |
17 |
Correct |
26 ms |
4016 KB |
Output is correct |
18 |
Correct |
57 ms |
7572 KB |
Output is correct |
19 |
Correct |
89 ms |
12884 KB |
Output is correct |
20 |
Incorrect |
3 ms |
852 KB |
Tour is not fun |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
300 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
300 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 |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
296 KB |
Output is correct |
31 |
Correct |
1 ms |
300 KB |
Output is correct |
32 |
Correct |
1 ms |
300 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Incorrect |
1 ms |
300 KB |
Repeated index |
35 |
Halted |
0 ms |
0 KB |
- |