#include <bits/stdc++.h>
#ifndef LOCAL
#include "longesttrip.h"
#endif
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
#ifdef LOCAL
vector<vector<int>> G_secret;
int n;
int count_query = 0;
bool are_connected(vector<int> a, vector<int> b) {
++count_query;
for (int i : a) {
for (int j : b) {
if (G_secret[i][j])
return true;
}
}
return false;
}
#endif
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n);
iota(all(p), 0);
}
int get(int a) {
if (p[a] == a)
return a;
return p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a), b = get(b);
p[a] = b;
}
};
vector<int> get_comp(int n, int v, dsu &d) {
vector<int> comp;
for (int i = 0; i < n; ++i) {
if (d.get(i) == v) {
comp.push_back(i);
}
}
return comp;
}
void add_comp(vector<int> &ans, vector<int> &comp, pair<int, int> end) {
ans.push_back(end.first);
for (int j : comp) {
if (j != end.first && j != end.second) {
ans.push_back(j);
}
}
if (end.first != end.second) {
ans.push_back(end.second);
}
}
vector<int> longest_trip(int n, int D) { // Случай, когда отдельная вершинка - 0
dsu d(n);
vector<vector<int>> path;
vector<pair<int, int>> ends;
ends.push_back({0, 0});
path.push_back({0});
vector<int> ost(n - 1);
iota(all(ost), 1);
while (true) {
int ind_comp = ost[0];
bool find = false;
bool was_merge = false;
for (int i = 0; i < (int) ost.size(); ++i) {
if (are_connected({ends.back().second}, get_comp(n, ost[i], d))) {
path.push_back(get_comp(n, ost[i], d));
int last_end = ends.back().second;
ends.emplace_back();
{
int L = -1, R = (int) path.back().size() - 1;
while (R - L > 1) {
// cout << L << ' ' << R << "!\n";
int mid = (R + L) / 2;
vector<int> tmp;
for (int j = 0; j <= mid; ++j) {
tmp.push_back(path.back()[j]);
}
if (tmp.size() && are_connected({last_end}, tmp)) {
R = mid;
} else {
L = mid;
}
}
ends.back().first = path.back()[R];
}
if (path.back().size() == 1) {
ends.back().second = ends.back().first;
} else {
if (ends.back().first != path.back()[0]) {
ends.back().second = path.back()[0];
} else {
ends.back().second = path.back().back();
}
}
swap(ost[i], ost.back());
ost.pop_back();
find = true;
break;
} else {
was_merge = true;
d.merge(ost[i], ind_comp);
swap(ost[i], ost.back());
ost.pop_back();
--i;
}
}
if (was_merge)
ost.push_back(ind_comp);
if (!ost.size()) {
vector<int> ans;
for (int i = 0; i < (int) path.size(); ++i) {
add_comp(ans, path[i], ends[i]);
}
// cout << "MEOW1\n";
return ans;
}
if (!find) {
vector<int> last_comp = get_comp(n, ost[0], d);
int V = -1;
vector<int> ost_graph;
for (auto i : path) {
for (int j : i) {
ost_graph.push_back(j);
}
}
{
int L = -1, R = (int) last_comp.size() - 1;
while (R - L > 1) {
// cout << L << ' ' << R << "!\n";
int mid = (R + L) / 2;
vector<int> tmp;
for (int j = 0; j <= mid; ++j) {
tmp.push_back(last_comp[j]);
}
if (tmp.size() && are_connected(ost_graph, tmp)) {
R = mid;
} else {
L = mid;
}
}
ends.back().first = last_comp[R];
}
// for (int i : last_comp) {
// if (are_connected({i}, ost_graph)) {
// V = i;
// break;
// }
// }
if (V == -1) {
vector<int> ans;
if (last_comp.size() > n - last_comp.size()) {
for (int i : last_comp)
ans.push_back(i);
} else {
for (auto i : path) {
for (int j : i)
ans.push_back(j);
}
}
return ans;
}
for (int i = 0; i < (int) path.size(); ++i) {
if (are_connected({V}, {ends[i].first})) {
vector<int> ans;
for (int j : last_comp) {
if (j != V) {
ans.push_back(j);
}
}
ans.push_back(V);
for (int j = i; j < (int) path.size(); ++j) {
add_comp(ans, path[j], ends[j]);
}
for (int j = 0; j < i; ++j) {
add_comp(ans, path[j], ends[j]);
}
// cout << "MEOW2\n";
return ans;
}
}
}
}
assert(0);
return {-1};
}
#ifdef LOCAL
int main()
{
int t;
cin >> t;
while (t--) {
count_query = 0;
int n, d;
cin >> n >> d;
G_secret.clear();
G_secret.resize(n, vector<int> (n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
cin >> G_secret[i][j];
G_secret[j][i] = G_secret[i][j];
}
}
cout << "MEOW\n";
auto res = longest_trip(n, d);
cout << res.size() << '\n';
// for (int i : res)
// cout << i << ' ';
cout << '\n';
cout << count_query << '\n';
// vector<int> p(n);
// iota(all(p), 0);
// int ans = 0;
// do {
// for (int i = 1; i <= n; ++i) {
// bool valid = true;
// for (int j = 0; j < i - 1; ++j) {
// if (!G_secret[p[j]][p[j + 1]]) {
// valid = false;
// }
// }
// if (valid) {
// ans = max(ans, i);
// }
// }
// } while (next_permutation(all(p)));
// if (res.size() != ans) {
// cout << "Попався\n";
// cout << n << ' ' << d << '\n';
// for (int i = 1; i < n; ++i) {
// for (int j = 0; j < i; ++j) {
// cout << G_secret[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int i : res)
// cout << i << ' ';
// cout << '\n';
// cout << "! " << ans << '\n';
// return 0;
// }
}
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
340 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| 3 |
Correct |
7 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
344 KB |
Output is correct |
| 6 |
Correct |
5 ms |
344 KB |
Output is correct |
| 7 |
Correct |
7 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
600 KB |
Output is correct |
| 9 |
Correct |
5 ms |
344 KB |
Output is correct |
| 10 |
Correct |
6 ms |
344 KB |
Output is correct |
| 11 |
Correct |
5 ms |
344 KB |
Output is correct |
| 12 |
Correct |
6 ms |
344 KB |
Output is correct |
| 13 |
Correct |
5 ms |
344 KB |
Output is correct |
| 14 |
Correct |
6 ms |
344 KB |
Output is correct |
| 15 |
Correct |
7 ms |
596 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
344 KB |
Incorrect |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
600 KB |
Output is correct |
| 4 |
Correct |
5 ms |
600 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
