#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[ce] - get_changes(e, ce);
}
} 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;
}
if (ans[ce] == -1) ans[ce] = 0;
for (auto e : path) {
if (ans[e] == -1)
ans[e] = ans[ce];
}
}
}
int par[N];
int root(int u) {
if (par[u] == u) return u;
return par[u] = root(par[u]);
}
bool merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) return false;
par[u] = v;
return true;
}
int query_adj(vector<int> &adj)
{
if (adj.empty()) return 0;
iota(par, par+n, 0);
vector<int> q;
for (auto e : adj) {
merge(U[e], V[e]);
q.push_back(e);
}
int cnt = 0;
for (auto e : T) {
if (merge(U[e], V[e])) {
cnt += ans[e];
q.push_back(e);
}
}
int ret = count_common_roads(q);
return ret-cnt;
}
void solve(vector<int> &adj, int cnt = -1)
{
if (cnt == -1)
cnt = query_adj(adj);
if (cnt == 0) {
for (auto e : adj)
ans[e] = 0;
return;
}
if (cnt == adj.size()) {
for (auto e : adj)
ans[e] = 1;
return;
}
int mid = adj.size()/2;
vector<int> L(adj.begin(), adj.begin()+mid);
vector<int> R(adj.begin()+mid, adj.end());
int lcnt = query_adj(L);
solve(L, lcnt);
solve(R, cnt-lcnt);
}
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);
}
// find answer for each node
for (int u = 0; u < n; ++u) {
vector<int> adj;
for (auto v : G[u]) {
if (ans[v.S] == -1)
adj.push_back(v.S);
}
solve(adj);
}
// return answer
vector<int> ret;
for (int i = 0; i < m; ++i) {
if (ans[i])
ret.push_back(i);
}
return ret;
}
Compilation message
simurgh.cpp: In function 'void solve(std::vector<int>&, int)':
simurgh.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cnt == adj.size()) {
~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
correct |
| 2 |
Correct |
3 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
416 KB |
correct |
| 4 |
Correct |
3 ms |
420 KB |
correct |
| 5 |
Runtime error |
1499 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
correct |
| 2 |
Correct |
3 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
416 KB |
correct |
| 4 |
Correct |
3 ms |
420 KB |
correct |
| 5 |
Runtime error |
1499 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
correct |
| 2 |
Correct |
3 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
416 KB |
correct |
| 4 |
Correct |
3 ms |
420 KB |
correct |
| 5 |
Runtime error |
1499 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1049600 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
correct |
| 2 |
Correct |
3 ms |
376 KB |
correct |
| 3 |
Correct |
2 ms |
416 KB |
correct |
| 4 |
Correct |
3 ms |
420 KB |
correct |
| 5 |
Runtime error |
1499 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
