#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> g[505];
int par[505];
int parId[505];
int high[505];
int color[505 * 505];
vector<int> tree;
int u[505 * 505], v[505 * 505];
struct Dsu {
int par[505];
void init() {
for (int i = 0; i < n; ++i) {
par[i] = i;
}
}
int find(int u) {
if (u != par[u]) {
par[u] = find(par[u]);
}
return par[u];
}
bool merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return false;
} else {
par[v] = u;
return true;
}
}
} d;
void dfs(int u) {
for (auto e : g[u]) {
int v, id;
tie(v, id) = e;
if (v != par[u]) {
par[v] = u;
parId[v] = id;
high[v] = high[u] + 1;
dfs(v);
}
}
}
vector<int> findPath(int u, int v) {
vector<int> ans;
while (u != v) {
if (high[u] > high[v]) {
ans.emplace_back(parId[u]);
u = par[u];
} else {
ans.emplace_back(parId[v]);
v = par[v];
}
}
cout << "FindPathOK\n";
return ans;
}
int get(vector<int> es) {
d.init();
for (int i : es) {
d.merge(u[i], v[i]);
}
int offset = 0;
for (int i : tree) {
if (d.merge(u[i], v[i])) {
offset += color[i];
es.push_back(i);
}
}
assert(es.size() == n - 1);
return count_common_roads(es) - offset;
}
vector<int> ans;
void solve(int cnt, vector<int> go) {
int n = go.size();
if (cnt == 0) {
return;
} else if (cnt == n) {
for (int i : go) {
ans.emplace_back(i);
}
return;
} else {
vector<int> lgo = vector<int>(go.begin(), go.begin() + (n / 2));
vector<int> rgo = vector<int>(go.begin() + (n / 2), go.end());
int lcnt = get(lgo);
int rcnt = cnt - lcnt;
solve(lcnt, lgo);
solve(rcnt, rgo);
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
::n = n;
m = u.size();
for (int i = 0; i < m; ++i) {
::u[i] = u[i];
::v[i] = v[i];
color[i] = -1;
}
d.init();
set<int> out;
for (int i = 0; i < m; ++i) {
if (d.merge(u[i], v[i])) {
tree.push_back(i);
g[u[i]].emplace_back(v[i], i);
g[v[i]].emplace_back(u[i], i);
} else {
out.insert(i);
}
}
dfs(0);
for (int i : out) {
vector<int> cur = findPath(u[i], v[i]);
bool flag = false;
for (int j : cur) {
if (color[j] == -1) {
flag = true;
}
}
if (!flag) {
continue;
}
cur.emplace_back(i);
int numEdge = -1;
for (int j : cur) {
if (color[j] != -1) {
vector<int> q;
for (int k : cur) if (j != k) {
q.emplace_back(k);
}
numEdge = get(q) + color[j];
break;
}
}
vector<pair<int, int>> vals;
for (int j : cur) {
if (color[j] == -1) {
vector<int> q;
for (int k : cur) if (j != k) {
q.emplace_back(k);
}
vals.emplace_back(j, get(q));
numEdge = max(numEdge, vals.back().second);
}
}
for (auto p : vals) {
color[p.first] = p.second < numEdge;
}
}
for (int i : tree) {
color[i] = abs(color[i]);
if (color[i]) {
ans.emplace_back(i);
}
}
for (int i = 0; i < n; ++i) {
vector<int> go;
for (int j : out) {
if (u[j] == i || v[j] == i) {
go.emplace_back(j);
}
}
if (go.size()) {
for (int j : go) {
out.erase(j);
}
solve(get(go), go);
}
}
return ans;
}
// g++ -std=c++14 grader.cpp simurgh.cpp
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from simurgh.cpp:3:
simurgh.cpp: In function 'int get(std::vector<int>)':
simurgh.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(es.size() == n - 1);
~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Security Violation! Don't try to hack |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
