#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
using pii = pair<int, int>;
#define F first
#define S second
const int N = 510;
const int M = N*(N-1)/2;
const int LIM = 30000;
int n, m;
vector<int> U, V; // edge list
vector<pii> G[N]; // adj list
vector<int> T; // tree edges
vector<pii> GT[N]; // tree adj list
bool is_tree[M];
int ans[M]; // answer to each edge (-1 = unknown)
int defcnt; // answer for the default spanning tree
int tick;
pii disc[N], low[N];
void dfs(int u, int p)
{
disc[u] = low[u] = pii(++tick, -1);
for (auto v : G[u]) {
if (!disc[v.F].F) {
// push edge to tree
is_tree[v.S] = true;
T.push_back(v.S);
GT[u].emplace_back(v.F, v.S);
GT[v.F].emplace_back(u, v.S);
// tarjan's algorithm
dfs(v.F, u);
low[u] = min(low[u], low[v.F]);
if (low[v.F].F > disc[u].F)
ans[v.S] = 1;
} else {
low[u] = min(low[u], pii(disc[v.F].F, v.S));
}
}
}
vector<int> find_path(int u, int e, int t)
{
if (u == t) {
vector<int> ret;
ret.push_back(e);
return ret;
}
for (auto v : GT[u]) if (v.S != e) {
vector<int> ret = find_path(v.F, v.S, t);
if (!ret.empty()) {
if (e != -1)
ret.push_back(e);
return ret;
}
}
return vector<int>();
}
int get_changes(int rem, int add)
{
vector<int> q(T);
q.erase(find(q.begin(), q.end(), rem));
q.push_back(add);
return count_common_roads(q) - defcnt;
}
void query_cycle(int ce)
{
if (ans[ce] != -1) return;
int s = U[ce], t = V[ce];
vector<int> path = find_path(s, -1, t);
// find edge in path that we already know answer to
int fnd = -1;
for (auto e : path) {
if (ans[e] != -1) {
fnd = e;
break;
}
}
if (fnd != -1) { // case where we can quickly determine ce's value
ans[ce] = ans[fnd] + get_changes(fnd, ce);
for (auto e : path) { // update other edge in path we don't know
if (ans[e] == -1)
ans[e] = ans[fnd] - get_changes(e, fnd);
}
} else { // don't know, so query everything in the cycle
for (auto e : path) {
int d = get_changes(e, ce);
if (d == 1)
ans[ce] = 1, ans[e] = 0;
else if (d == -1)
ans[ce] = 0, ans[e] = 1;
}
for (auto e : path) {
if (ans[e] == -1)
ans[e] = ans[ce];
}
}
}
vector<int> find_roads(int _n, vector<int> _U, vector<int> _V)
{
// create adj list
n = _n;
U = _U, V = _V;
m = U.size();
for (int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
G[u].emplace_back(v, i);
G[v].emplace_back(u, i);
}
// build dfs tree and find answer for the tree
fill(ans, ans+m, -1);
dfs(1, -1);
defcnt = count_common_roads(T);
/*for (int i = 0; i < n; ++i) {
if (low[i].S != -1)
query_cycle(low[i].S);
}*/
// test subtask
for (int i = 0; i < m; ++i) {
if (!is_tree[i])
query_cycle(i);
}
// return answer
vector<int> ret;
for (int i = 0; i < m; ++i) {
if (ans[i])
ret.push_back(i);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
correct |
| 2 |
Incorrect |
2 ms |
492 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
