#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
vector<vector<pii>> adj;
vector<pii> par;
vector<int> dep;
vector<bool> vis;
vector<bool> ontree;
vector<int> ans;
int n, m;
void dfstree(int u = 1, int pp = 0, int d = 1) {
dep[u] = d;
vis[u] = true;
for (pii v : adj[u]) {
if (vis[v.ff]) continue;
par[v.ff] = {u, v.ss};
ontree[v.ss] = true;
dfstree(v.ff, u, d + 1);
}
}
set<int> qry;
void del(int x) { qry.erase(qry.find(x)); }
void add(int x) { qry.insert(x); }
int ask() {
vector<int> r;
for (int x : qry) r.pb(x);
return count_common_roads(r);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
n = N; m = (int)(U.size());
adj.resize(n + 1);
par.clear(); par.resize(n + 1, make_pair(0, 0));
dep.clear(); dep.resize(n + 1, 0);
vis.clear(); vis.resize(n + 1, false);
ontree.clear(); ontree.resize(m, false);
ans.clear(); ans.resize(m, -1);
for (int i = 0; i < m; i++) {
U[i]++; V[i]++;
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
dfstree();
for (int i = 0; i < m; i++) {
if (ontree[i]) {
// cerr << "EDGE " << i << " ON DFS TREE" << endl;
qry.insert(i);
}
}
int INIT = ask();
// cerr << INIT << endl;
for (int i = 0; i < m; i++) {
if (dep[U[i]] > dep[V[i]]) swap(U[i], V[i]);
if (ontree[i]) continue;
vector<int> chain;
int cur = V[i];
while (cur != U[i]) {
chain.pb(par[cur].ss);
cur = par[cur].ff;
}
// cerr << "edge " << i << ": ";
// for (int x : chain) cerr << x << ' ';
// cerr << endl;
int len = chain.size();
int cnt = 0;
for (int x : chain) cnt += (ans[x] != -1);
if (cnt == 0) {
// everything unknown: query everything
vector<int> res;
add(i);
for (int x : chain) {
del(x);
res.pb(ask());
add(x);
}
del(i);
// cannot be all 1s, so if all equal assign 0s
int maxi = INIT;
for (int x : res) maxi = max(maxi, x);
// cerr << "checking ";
// for (int x : chain) cerr << x << ' ';
// cerr << ", maxi = " << maxi << endl;
ans[i] = maxi - INIT;
for (int i = 0; i < len; i++) {
ans[chain[i]] = maxi - res[i];
}
} else if (cnt < len) {
// more than one known: query everything else
pii known = {-1, -1};
for (int x : chain) {
if (ans[x] != -1) {
known = {x, ans[x]};
break;
}
}
// query everything else except for this, calculate expected sum
del(known.ff); add(i);
int TOT = ask() + known.ss;
add(known.ff);
// calcuate i from TOT and INIT
ans[i] = TOT - INIT;
// erase every unknown edge and calculate
for (int x : chain) {
if (ans[x] != -1) continue;
del(x);
ans[x] = TOT - ask();
add(x);
}
del(i);
}
}
for (int i = 0; i < m; i++) {
// check for bridges
if (ontree[i] && ans[i] == -1) ans[i] = 1;
}
vector<int> edges;
auto test = [&](int lb, int rb) -> bool {
int expect = INIT;
for (int i = lb; i <= rb; i++) {
int u, v = U[edges[i]], V[edges[i]];
// u is ancestor of v -> remove {v, par[v]}
del(par[v].ss); expect -= ans[par[v].ss];
add(edges[i]);
}
bool ret = (ask() > expect);
for (int i = lb; i <= rb; i++) {
int u, v = U[edges[i]], V[edges[i]];
add(par[v].ss);
del(edges[i]);
}
return ret;
};
// query remaining edges
for (int u = 1; u <= n; u++) {
edges.clear();
for (pii v : adj[u]) {
if (v.ff > u && ans[v.ss] == -1) edges.pb(v.ss);
}
if (edges.empty()) continue;
while (test(0, (int)(edges.size()) - 1)) {
int lb = 0, rb = (int)(edges.size()) - 1;
while (lb < rb) {
int mid = (lb + rb) >> 1;
if (test(lb, mid)) rb = mid;
else lb = mid + 1;
}
// edges[lb] is answer
ans[edges[lb]] = 1;
edges.erase(edges.begin() + lb);
}
}
vector<int> fin;
for (int i = 0; i < m; i++) {
if (ans[i] == 1) fin.pb(i);
}
// cerr << "ANSWER: ";
// for (int x : fin) cerr << x << ' ';
// cerr << endl;
return fin;
}
Compilation message
simurgh.cpp: In lambda function:
simurgh.cpp:126:8: warning: unused variable 'u' [-Wunused-variable]
126 | int u, v = U[edges[i]], V[edges[i]];
| ^
simurgh.cpp:126:28: warning: unused variable 'V' [-Wunused-variable]
126 | int u, v = U[edges[i]], V[edges[i]];
| ^
simurgh.cpp:133:8: warning: unused variable 'u' [-Wunused-variable]
133 | int u, v = U[edges[i]], V[edges[i]];
| ^
simurgh.cpp:133:28: warning: unused variable 'V' [-Wunused-variable]
133 | int u, v = U[edges[i]], V[edges[i]];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
