#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#include "simurgh.h"
//#define local
using namespace std;
int n,m;
vi u,v,adj[505];
bool good[25500],vis[505]; // if good[i] = 1, edge[u[i]v[i] ] = good
int type[25500];
map<pii,int> id;
set<int> query;
int tin[505],tout[505],timer,w[505],P[505],num,wow[25005];
#ifdef local
int count_common_roads(vector<int> v) {
int ans = 0;
cout <<"ASK:\t";
for (int i : v) cout << i <<' ';
cout << endl ;
for (int i : v) ans += wow[i];
return ans;
}
#endif
//////////////
int ask() {
vi v;
for (int i : query) v.pb(i);
int x = count_common_roads(v);
return x;
}
//////////////
void erase(int a,int b) {
query.erase(id[{a,b}]);
}
void insert(int a,int b) {
query.insert(id[{a,b}]);
}
///////////////
void jartidfs(int v) {
vis[v] = 1;
for (int i : adj[v]) {
if (!vis[i]) {
insert(v,i);
jartidfs(i);
}
}
}
void dfs(int v,int p) {
int z = 0;
P[v] = p;
vi parents,erased;
if (p != -1) parents.pb(p);
vis[v] = 1;
tin[v] = w[v] = z = ++timer;
for (int i : adj[v]) {
if (i == p) continue;
if (vis[i]) {
if (tin[i] < tin[v]) {
z = min(z,tin[i]);
parents.pb(i);
}
}
else {
dfs(i,v);
w[v] = min(w[v],w[i]);
}
}
vector<pii> dif,same;
set <int> good,bad;
sort(parents.begin(),parents.end(),[&](int i,int j) {
return tin[i] > tin[j];
});
// cout << v <<'\t';
//for (int i : parents) cout << i <<' ';
cout << endl;
for (int i = 1; i < parents.size();i++) {
int cnt = num;
int curnode = v;
insert(v,parents[i]);
P[v] = parents[i-1];
int id1 = id[{v,parents[i]}];
do{
erase(curnode,P[curnode]);
// if(query.size()== 4){
// cout<<v <<'s';
// }
num = ask();
int id2 = id[{curnode,P[curnode]}];
if (cnt < num) {
good.insert(id1);
bad.insert(id2);
}
else if (cnt > num) {
bad.insert(id1);
good.insert(id2);
}
else {
same.pb({id1,id2});
}
if (P[curnode] != parents[i])
insert(curnode,P[curnode]);
else erased.pb(id[{curnode,parents[i]}]);
curnode = P[curnode];
}while(curnode != parents[i]);
//query.erase(id[{parents[i-1],v}]);
//query.insert(id[{parents[i],v}]);
//num = ask();
//if (num)
}
for (int i : erased) query.insert(i);
// for(int i = 1 ; i < parents.size();i++)
while(parents.size() >= 2) {
erase(v,parents.back());
parents.pop_back();
}
vi seen(505);
vector<vi> e(505);
for (auto i : same) {
e[i.fi].pb(i.se);
e[i.se].pb(i.fi);
}
for (int i : good) {
queue<int> q;
type[i] = 1;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
for (int i : bad) {
queue<int> q;
type[i] = -1;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
P[v] = p;
if (good.empty() && bad.empty() && w[v] <= tin[v]) {
for (int i : parents) type[id[{v,i}]] = 1;
if (parents.size()){
int t = 10;
for (int i = v; i != parents.back() && t ; t--,i = P[i]) {
type[id[{i,P[i]}]] = 1;
}
}
}
w[v] = min(w[v],z);
}
void preprocess(int n1,vi u1, vi v1) {
m = u1.size(); n = n1;
u = u1; v = v1;
for (int i = 0; i < m; i++) {
id[{u[i],v[i]}] = id[{v[i],u[i]}] = i;
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
}
}
vi find_roads(int n1, vi u1, vi v1) {
preprocess(n1,u1,v1);
jartidfs(0);
num = ask();
memset(vis,0,sizeof vis);
vector<int> g = {-1};
// return g;
dfs(0,-1);
// vi ans(n - 1);
//int common = count_common_roads(r);
// if(common == n - 1)
// return r;
// r[0] = n - 1;
vi ans;
for (int i = 0; i < m; i++) if (type[i] == 1) ans.pb(i);
ans.resize(n-1);
return ans;
}
#ifdef local
main() {
int n,m; cin >> n >> m;
vi u,v;
for (int i = 0;i < m ;i++ ) {
int a, b; cin >> a >> b;
u.pb(a);
v.pb(b);
}
for (int i = 0; i < n - 1; i++) {
int a; cin >> a;
wow[a] = 1;
}
vector<int> ans = find_roads(n,u,v);
for (int i :ans ) cout << i <<' ';
}
#endif
Compilation message
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < parents.size();i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:134:8: warning: unused variable 'v' [-Wunused-variable]
int v = q.front();
^
simurgh.cpp:149:8: warning: unused variable 'v' [-Wunused-variable]
int v = q.front();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
