#include "simurgh.h"
#include<vector>
#include<queue>
#include<utility>
#include<iostream>
#define MAXN 505
using namespace std;
vector<pair<int,int> > adj[MAXN], Tree[MAXN]; //to, edge id
vector<int> TreeId, Ans;
int N,M,X, rt = 0; //spanning tree count
int low[MAXN], lowid[MAXN], par[MAXN], parid[MAXN], depth[MAXN], res[MAXN];
bool golden[MAXN], vis[MAXN], vis2[MAXN], done[MAXN];
//tree making phrase
void dfs(int u) { //make dfs tree
vis[u] = true;
for (auto v: adj[u]) {
if (!vis[v.first]) {
TreeId.push_back(v.second);
Tree[u].push_back(v);
Tree[v.first].push_back({u,v.second});
depth[v.first] = depth[u] + 1;
par[v.first] = u, parid[v.first] = v.second;
dfs(v.first);
}
}
}
void solveTree(int u) { //solve dfs tree's identity
vis2[u] = true, low[u] = u;
int chd_low = u;
for (auto v: adj[u]) {
if (vis2[v.first] and v.first != par[u]) {
if (depth[low[u]] > depth[v.first]) {
low[u] = v.first;
lowid[u] = v.second;
}
} else if (!vis2[v.first]) {
solveTree(v.first);
if (depth[chd_low] > depth[low[v.first]]) {
chd_low = low[v.first];
}
}
}
if (low[u] == u && chd_low == u) {
golden[parid[u]] = true;
done[parid[u]] = true; //which edges u-par(u) have been solved?
} else if (depth[low[u]] >= depth[chd_low]) {
low[u] = chd_low; //relax
} else {
int cur = u, seen_normal = false, t1=false, t2=false, t3=false;
while (cur != low[u] && cur != rt) {
if (!done[cur] || (!seen_normal && !golden[parid[cur]])) {
vector<int> query;
query.push_back(lowid[u]);
for (int i=0; i<N-1; i++) {
if (TreeId[i] != parid[cur]) {
query.push_back(TreeId[i]);
}
}
res[cur] = count_common_roads(query);
if (res[cur] == X-1) {
t1 = true;
} else if (res[cur] == X) {
t2 = true;
} else if (res[cur] == X+1) {
t3 = true;
}
if (done[cur]) {seen_normal = true;}
}
cur = par[cur];
}
cur = u;
while (cur != low[u] && cur != rt) {
if (!done[parid[cur]]) {
done[parid[cur]] = true;
if (t1 && res[cur] == X-1) {
golden[parid[cur]] = true;
} else if (t3 && res[cur] == X) {
golden[parid[cur]] = true;
}
}
cur = par[cur];
}
}
}
//Solving phrase
int Num(vector<pair<int,int> > Eset, int v) {
int C = Eset.size(), D = 0; //count golden in Eset, adj of v
bool vis3[MAXN] = {};
queue<int> Q;
vector<int> Query;
for (auto e: Eset) {
Tree[v].push_back(e);
}
Q.push(v), vis3[v] = true;
while (Q.size()) {
int cur = Q.front();
Q.pop();
for (int i=Tree[cur].size()-1; i>=0; i--) {
if (!vis3[Tree[cur][i].first]) {
vis3[Tree[cur][i].first] = true;
Q.push(Tree[cur][i].first);
Query.push_back(Tree[cur][i].second);
if (done[Tree[cur][i].second]) {
D += (int) golden[Tree[cur][i].second];
}
}
}
}
for (int i=0; i<C; i++) {
Tree[v].pop_back();
}
return(count_common_roads(Query) - D);
}
void FindGolden(int u) {
vector <pair<int,int> > todo;
for (auto v: adj[u]) {
if (!done[v.second]) {
todo.push_back(v); //all not done
}
}
int deg = Num(todo, u);
for (int i=0; i<deg; i++) {
vector <pair<int,int> > Maybe;
for (auto v: adj[u]) {
if (!done[v.second]) {
Maybe.push_back(v);
}
}
int lo = 0, hi = Maybe.size()-1;
while (lo != hi) {
int mid = (lo + hi) >> 1;
vector<pair<int,int> > query;
for (int j=lo; j<=mid; j++) {
query.push_back(Maybe[j]);
}
if (Num(query, u)) {
hi = mid;
} else {
lo = mid + 1;
}
}
golden[Maybe[hi].second] = true;
done[Maybe[hi].second] = true;
}
for (auto v: adj[u]) {
done[v.second] = true;
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
N = n, M = u.size();
for (int i=0; i<M; i++) {
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
par[rt] = -1, dfs(rt);
X = count_common_roads(TreeId);
solveTree(rt);
for (int i=0; i<N; i++) {
FindGolden(i); //find all golden edges adj to i
}
for (int i=0; i<M; i++) {
if (golden[i]) {
Ans.push_back(i);
}
}
return(Ans);
}
Compilation message
simurgh.cpp: In function 'void solveTree(int)':
simurgh.cpp:51:53: warning: variable 't2' set but not used [-Wunused-but-set-variable]
int cur = u, seen_normal = false, t1=false, t2=false, t3=false;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
correct |
| 2 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
