#include "simurgh.h"
#include <algorithm>
using namespace std;
typedef pair<int, int> pi;
struct road {
int i, x;
};
int n, m;
const int MAXM = 500 * 499 / 2;
vector<road> edge[500];
pi es[MAXM];
bool dfsTree[MAXM];
bool backGraph[MAXM];
vector<int> dfsQ;
int par[500];
int parEdge[500];
int dep[500];
int back[500];
int backEdge[500];
int ord = 0, base;
int royal[MAXM];
int sub[500];
int uf[500];
void dfs(int x, int p) {
dep[x] = ++ord;
back[x] = dep[x];
backEdge[x] = -1;
for (road i : edge[x]) {
if (dep[i.x] != 0) {
if (i.x != p && dep[i.x] < back[x]) {
back[x] = dep[i.x];
backEdge[x] = i.i;
}
continue;
}
dfsTree[i.i] = true;
dfsQ.push_back(i.i);
par[i.x] = x;
parEdge[i.x] = i.i;
dfs(i.x, x);
if (back[i.x] == dep[i.x]) royal[i.i] = 1;
else if (back[i.x] < back[x]) {
back[x] = back[i.x];
backEdge[x] = backEdge[i.x];
}
}
if (back[x] < dep[x]) backGraph[backEdge[x]] = true;
}
int find(int x) {
if (uf[x] != x) return uf[x] = find(uf[x]);
return x;
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
uf[x] = y;
return true;
}
int question(const vector<int> &vt) {
vector<int> qs;
int other = 0;
for (int i = 0; i < n; ++i) uf[i] = i;
for (int i : vt) {
qs.push_back(i);
merge(es[i].first, es[i].second);
}
for (int i : dfsQ) {
if (merge(es[i].first, es[i].second)) {
qs.push_back(i);
if (royal[i] == 1) ++other;
}
}
return count_common_roads(qs) - other;
}
void bsearch(const vector<int> &vt, int s, int e, int c) {
if (c == 0) {
for (int i : vt) royal[i] = -1;
return;
}
if (c == e - s + 1) {
for (int i : vt) royal[i] = 1;
return;
}
vector<int> qs;
int m = (s + e) / 2;
for (int i = s; i <= m; ++i) qs.push_back(vt[i]);
int d = question(qs);
bsearch(vt, s, m, d);
bsearch(vt, m + 1, e, c - d);
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
n = N;
m = u.size();
for (int i = 0; i < m; ++i) {
es[i] = pi(u[i], v[i]);
edge[u[i]].push_back({ i, v[i] });
edge[v[i]].push_back({ i, u[i] });
}
dfs(0, -1);
base = count_common_roads(dfsQ);
vector<pi> es;
for (int i = 0; i < m; ++i) {
if (backGraph[i]) es.push_back(pi(min(dep[u[i]], dep[v[i]]), i));
}
sort(es.begin(), es.end());
for (pi i : es) {
int s = u[i.second], e = v[i.second];
if (dep[s] < dep[e]) swap(s, e);
int j = s;
bool allZero = true;
while (par[j] != e) {
if (royal[parEdge[j]] == 0) {
vector<int> qs;
for (int k : dfsQ) {
if (k != parEdge[j]) qs.push_back(k);
}
qs.push_back(i.second);
sub[j] = count_common_roads(qs) - base;
if (sub[j] != 0) {
allZero = false;
royal[parEdge[j]] = -sub[j];
royal[i.second] = sub[j];
}
}
else allZero = false;
j = par[j];
}
vector<int> qs;
for (int k : dfsQ) {
if (k != parEdge[j]) qs.push_back(k);
}
qs.push_back(i.second);
sub[j] = count_common_roads(qs) - base;
if (royal[parEdge[j]] != 0) {
allZero = false;
royal[i.second] = royal[parEdge[j]] + 2 * sub[j];
}
else if (sub[j] != 0) {
allZero = false;
royal[parEdge[j]] = -sub[j];
royal[i.second] = sub[j];
}
if (allZero) {
j = s;
while (j != e) {
royal[parEdge[j]] = -1;
j = par[j];
}
royal[i.second] = -1;
continue;
}
j = s;
while (j != e) {
if (royal[parEdge[j]] == 0) royal[parEdge[j]] = royal[i.second] - 2 * sub[j];
j = par[j];
}
}
for (int i = 0; i < n; ++i) {
vector<int> es;
for (road j : edge[i]) {
if (royal[j.i] == 0) es.push_back(j.i);
}
bsearch(es, 0, es.size() - 1, question(es));
}
vector<int> ret;
for (int i = 0; i < m; ++i) {
if (royal[i] == 1) ret.push_back(i);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3668 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3668 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3668 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3668 KB |
correct |
| 2 |
Incorrect |
0 ms |
3668 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3668 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
