#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include "longesttrip.h"
using namespace std;
map<pair<vector<int>, vector<int>>, bool> memo;
bool safe_are_connected(vector<int> S_left, vector<int> S_right) {
if(S_left.size() == 0 || S_right.size() == 0) return false;
if(memo.count(make_pair(S_left, S_right))) {
return memo[make_pair(S_left, S_right)];
}
bool ret = are_connected(S_left, S_right);
memo[make_pair(S_left, S_right)] = ret;
memo[make_pair(S_right, S_left)] = ret;
return ret;
}
vector<vector<int>> create_adj(
int N, vector<int> nodes, vector<pair<int, int>> edges
) {
vector<vector<int>> adj(N);
vector<bool> in_nodes(N, false);
for(auto n: nodes) in_nodes[n] = true;
for(auto e: edges) {
if(!in_nodes[e.first] || !in_nodes[e.second]) continue;
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
return adj;
}
void add_edge(int u, int v, vector<set<int>> &adj_set) {
adj_set[u].insert(v);
adj_set[v].insert(u);
}
void remove_edge(int u, int v, vector<set<int>> &adj_set) {
adj_set[u].erase(v);
adj_set[v].erase(u);
}
int only_par(int u, vector<set<int>> &adj_set, int from = -1) {
assert(adj_set[u].size() <= 2);
for(auto nei: adj_set[u]) {
if(nei != from) return nei;
}
return -1;
}
void prune_tree(
int l1, int l2, int l3, vector<int> &leaves, vector<set<int>> &adj_set
) {
leaves.push_back(l3);
int u = l1, v = l2;
while(adj_set[u].size() == 1) {
int pu = only_par(u, adj_set);
remove_edge(u, pu, adj_set);
add_edge(v, u, adj_set);
v = u;
u = pu;
}
leaves.push_back(v);
}
vector<int> solve_tree(int N, vector<int> nodes, vector<vector<int>> adj) {
vector<set<int>> adj_set(N);
for(int i = 0; i < N; i++) {
adj_set[i] = set<int>(adj[i].begin(), adj[i].end());
}
// We assume that the tree is connected here
vector<int> leaves;
for(auto node: nodes) {
if(adj_set[node].size() == 1) {
leaves.push_back(node);
}
}
mt19937 mt(42);
while(leaves.size() >= 3) {
shuffle(leaves.begin(), leaves.end(), mt);
int l1 = leaves.back();
leaves.pop_back();
int l2 = leaves.back();
leaves.pop_back();
int l3 = leaves.back();
leaves.pop_back();
if(safe_are_connected({l1}, {l2})) {
prune_tree(l1, l2, l3, leaves, adj_set);
} else if(safe_are_connected({l1}, {l3})) {
prune_tree(l1, l3, l2, leaves, adj_set);
} else {
// Delta >= 1, means that l2 and l3 are connected
prune_tree(l2, l3, l1, leaves, adj_set);
}
}
// for(auto node: nodes) {
// cerr << node << "| ";
// for(auto nei: adj_set[node]) {
// cerr << nei << " ";
// }
// cerr << endl;
// }
// It's a path
vector<int> path;
vector<bool> used(N, false);
int u = leaves[0];
int last = -1;
while(u != -1) {
path.push_back(u);
used[u] = true;
int nlast = u;
u = only_par(u, adj_set, last);
last = nlast;
}
if(leaves.size() == 2) {
u = leaves[1];
vector<int> rev_path;
while(!used[u]) {
rev_path.push_back(u);
int nlast = u;
u = only_par(u, adj_set, last);
last = nlast;
}
reverse(rev_path.begin(), rev_path.end());
path.insert(path.end(), rev_path.begin(), rev_path.end());
}
return path;
}
pair<int, int> find_one_edge_old(
vector<int> S_left, vector<int> S_right, mt19937 &mt
) {
assert(S_left.size() >= 1 && S_right.size() >= 1);
if(S_left.size() == 1 && S_right.size() == 1) {
return {S_left[0], S_right[0]};
}
shuffle(S_left.begin(), S_left.end(), mt);
shuffle(S_right.begin(), S_right.end(), mt);
int mid_left = S_left.size() / 2;
int mid_right = S_right.size() / 2;
vector<int> left_left(S_left.begin(), S_left.begin() + mid_left);
vector<int> left_right(S_left.begin() + mid_left, S_left.end());
vector<int> right_left(S_right.begin(), S_right.begin() + mid_right);
vector<int> right_right(S_right.begin() + mid_right, S_right.end());
if(safe_are_connected(left_left, right_left)) {
return find_one_edge_old(left_left, right_left, mt);
} else if(safe_are_connected(left_left, right_right)) {
return find_one_edge_old(left_left, right_right, mt);
} else if(safe_are_connected(left_right, right_left)) {
return find_one_edge_old(left_right, right_left, mt);
} else {
return find_one_edge_old(left_right, right_right, mt);
}
}
pair<int, int> find_one_edge(
vector<int> S_left, vector<int> S_right, mt19937 &mt
) {
assert(S_left.size() >= 1 && S_right.size() >= 1);
if(S_left.size() == 1 && S_right.size() == 1) {
return {S_left[0], S_right[0]};
}
if(S_left.size() < S_right.size()) {
swap(S_left, S_right);
}
shuffle(S_left.begin(), S_left.end(), mt);
int mid_left = S_left.size() / 2;
vector<int> left_left(S_left.begin(), S_left.begin() + mid_left);
vector<int> left_right(S_left.begin() + mid_left, S_left.end());
if(safe_are_connected(left_left, S_right)) {
return find_one_edge(left_left, S_right, mt);
} else {
return find_one_edge(left_right, S_right, mt);
}
}
vector<int> longest_trip(int N, int D) {
assert(D >= 1);
memo.clear();
vector<int> comps[2];
vector<pair<int, int>> edges;
vector<int> order(N);
iota(order.begin(), order.end(), 0);
mt19937 mt(43);
shuffle(order.begin(), order.end(), mt);
comps[0].push_back(order[0]);
int other = 1;
int tail_0 = order[0];
while(true) {
while(other < N && safe_are_connected({tail_0}, {order[other]})) {
comps[0].push_back(order[other]);
edges.push_back({tail_0, order[other]});
tail_0 = order[other];
other++;
}
if(other == N) {
vector<int> all_nodes(N);
iota(all_nodes.begin(), all_nodes.end(), 0);
auto adj = create_adj(N, all_nodes, edges);
return solve_tree(N, all_nodes, adj);
} else {
// Maybe we have two components
comps[1].push_back(order[other]);
int tail_1 = order[other];
other++;
bool first_is_free = true;
while(other < N && safe_are_connected({tail_1}, {order[other]})) {
comps[1].push_back(order[other]);
edges.push_back({tail_1, order[other]});
tail_1 = order[other];
other++;
first_is_free = false;
}
if(other < N) {
if(!first_is_free && safe_are_connected({tail_0}, {tail_1})) {
edges.push_back({tail_0, tail_1});
reverse(comps[1].begin(), comps[1].end());
comps[0].insert(comps[0].end(), comps[1].begin(), comps[1].end());
tail_0 = comps[0].back();
comps[1].clear();
comps[1] = {order[other]};
tail_1 = order[other];
other++;
} else {
edges.push_back({tail_0, order[other]});
comps[0].push_back(order[other]);
tail_0 = order[other];
other++;
}
}
while(other < N) {
vector<pair<int, int>> opts = {{tail_0, 0}, {tail_1, 1}};
if(mt() % 2 == 0) {
swap(opts[0], opts[1]);
}
bool try_other = false;
int group = opts[0].second, tail = opts[0].first;
if(safe_are_connected({tail}, {order[other]})) {
comps[group].push_back(order[other]);
edges.push_back({tail, order[other]});
if(group == 0) {
tail_0 = order[other];
} else {
tail_1 = order[other];
}
try_other = true;
} else {
group = opts[1].second, tail = opts[1].first;
comps[group].push_back(order[other]);
edges.push_back({tail, order[other]});
if(group == 0) {
tail_0 = order[other];
} else {
tail_1 = order[other];
}
}
group = opts[1].second, tail = opts[1].first;
if(try_other && safe_are_connected({tail}, {order[other]})) {
edges.push_back({tail, order[other]});
// Merge groups
reverse(comps[1].begin(), comps[1].end());
comps[0].insert(
comps[0].end(), comps[1].begin(), comps[1].end()
);
comps[1].clear();
tail_0 = comps[0].back();
other++;
break;
}
other++;
}
if(other == N) {
if(safe_are_connected(comps[0], comps[1])) {
edges.push_back(find_one_edge(comps[0], comps[1], mt));
vector<int> all_nodes(N);
iota(all_nodes.begin(), all_nodes.end(), 0);
auto adj = create_adj(N, all_nodes, edges);
return solve_tree(N, all_nodes, adj);
}
// Two disjoint paths, so just get the longer one
if(comps[0].size() < comps[1].size()) swap(comps[0], comps[1]);
auto adj = create_adj(N, comps[0], edges);
return solve_tree(N, comps[0], adj);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
8 ms |
600 KB |
Output is correct |
| 4 |
Correct |
6 ms |
600 KB |
Output is correct |
| 5 |
Correct |
7 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| 2 |
Correct |
8 ms |
596 KB |
Output is correct |
| 3 |
Correct |
7 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
600 KB |
Output is correct |
| 6 |
Correct |
9 ms |
344 KB |
Output is correct |
| 7 |
Correct |
7 ms |
344 KB |
Output is correct |
| 8 |
Correct |
7 ms |
612 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1124 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1056 KB |
Output is correct |
| 11 |
Correct |
6 ms |
608 KB |
Output is correct |
| 12 |
Correct |
7 ms |
604 KB |
Output is correct |
| 13 |
Correct |
8 ms |
976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
356 KB |
Output is correct |
| 3 |
Correct |
5 ms |
356 KB |
Output is correct |
| 4 |
Correct |
6 ms |
612 KB |
Output is correct |
| 5 |
Correct |
6 ms |
356 KB |
Output is correct |
| 6 |
Correct |
11 ms |
356 KB |
Output is correct |
| 7 |
Correct |
8 ms |
356 KB |
Output is correct |
| 8 |
Correct |
6 ms |
612 KB |
Output is correct |
| 9 |
Correct |
6 ms |
620 KB |
Output is correct |
| 10 |
Correct |
6 ms |
628 KB |
Output is correct |
| 11 |
Correct |
6 ms |
612 KB |
Output is correct |
| 12 |
Correct |
6 ms |
856 KB |
Output is correct |
| 13 |
Correct |
6 ms |
864 KB |
Output is correct |
| 14 |
Correct |
9 ms |
356 KB |
Output is correct |
| 15 |
Correct |
9 ms |
356 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
356 KB |
Incorrect |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
356 KB |
Output is correct |
| 2 |
Correct |
6 ms |
356 KB |
Output is correct |
| 3 |
Correct |
5 ms |
356 KB |
Output is correct |
| 4 |
Correct |
6 ms |
612 KB |
Output is correct |
| 5 |
Correct |
6 ms |
344 KB |
Output is correct |
| 6 |
Correct |
10 ms |
596 KB |
Output is correct |
| 7 |
Correct |
10 ms |
600 KB |
Output is correct |
| 8 |
Correct |
7 ms |
344 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1144 KB |
Output is correct |
| 11 |
Correct |
6 ms |
856 KB |
Output is correct |
| 12 |
Correct |
6 ms |
628 KB |
Output is correct |
| 13 |
Correct |
6 ms |
968 KB |
Output is correct |
| 14 |
Correct |
9 ms |
344 KB |
Output is correct |
| 15 |
Correct |
9 ms |
344 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 17 |
Halted |
0 ms |
0 KB |
- |
