#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_roads(int n, vector<int> eu, vector<int> ev) {
int cc;
vector<int> p(n), sz(n);
function<int(int)> get = [&](int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
};
auto unite = [&](int u, int v) {
u = get(u); v = get(v);
if (u == v) {
return false;
}
if (sz[u] > sz[v]) {
swap(u, v);
}
--cc;
p[u] = v;
sz[v] += sz[u];
return true;
};
auto init_dsu = [&]() {
cc = n;
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
};
auto simulate = [&](vector<int> edges) {
assert((int) edges.size() == n - 1);
init_dsu();
for (int i = 0; i < n - 1; ++i) {
unite(eu[i], ev[i]);
}
};
int m = (int) eu.size();
init_dsu();
vector<int> in_tree, out_tree;
for (int i = 0; i < m; ++i) {
if (unite(eu[i], ev[i])) {
in_tree.push_back(i);
} else {
out_tree.push_back(i);
}
}
int x = count_common_roads(in_tree);
vector<int> state(m, -1);
for (int i : out_tree) {
//~ cout << "tree: ";
//~ for (int j : in_tree) {
//~ cout << j << ' ';
//~ }
//~ cout << endl;
vector<int> unknown;
state[i] = 0;
assert((int) in_tree.size() == n - 1);
for (int j = 0; j < n - 1; ++j) {
int label = in_tree[j];
vector<int> tmp = in_tree;
tmp.erase(tmp.begin() + j);
tmp.push_back(i);
simulate(tmp);
if (cc != 1) {
continue;
}
int y = count_common_roads(tmp);
if (state[label] == -1) {
if (y > x) {
state[label] = 0;
state[i] = 1;
in_tree = tmp;
x = y;
break;
} else if (y == x) {
unknown.push_back(label);
} else {//y < x
state[label] = 1;
state[i] = 0;//doesn't matter
break;
}
} else {
if (state[label] == 1) {
continue;
}
assert(state[label] == 0);
//state[label] = 0
if (y > x) {
x = y;
state[i] = 1;
in_tree = tmp;
} else {
//~ cout << "i, label, y, x: " << i << ' ' << label << ' ' << y << ' ' << x << endl;
//~ cout << "wut: " << i << endl;
assert(y == x);
state[i] = 0;//doesn't matter
}
break;
}
}
//~ cout << "I: " << i << ' ' << state[i] << endl;
//~ cout << "same: ";
//~ for (int label : unknown) {
//~ cout << "label: " << label << ' ';
//~ state[label] = state[i];
//~ }
//~ cout << endl;
//~ cout << "STATE: ";
//~ for (int j = 0; j < m; ++j) {
//~ cout << state[j] << ' ';
//~ }
//~ cout << endl;
//~ cout << "i, state[i]: " << i << ' ' << state[i] << endl;
}
return in_tree;
}
//~ int common = count_common_roads(r);
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
