#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
//#define local
#ifndef local
#include "simurgh.h"
#endif
using namespace std;
int n,m;
vi u,v,adj[505],rlans;
bool good[255000],vis[505]; // if good[i] = 1, edge[u[i]v[i] ] = good
set<pair<int,int> > SM;
int type[255000];
map<pii,int> id;
set<int> query;
int tin[505],tout[505],timer,w[505],P[505],num,wow[250005];
#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;
sort(parents.begin(),parents.end(),[&](int i,int j) {
return tin[i] > tin[j];
});
int s = 0;
// cout << v <<'\t';
//for (int i : parents) cout << i <<' ';
cout << endl;
for (int i = 1; i < parents.size();i++) {
int cnt = num = ask();
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();
// if (num == n-1) {
// rlans.clear();
// for (int i :query) rlans.pb(i);
// }
int id2 = id[{curnode,P[curnode]}];
if (cnt < num) {
type[id1] = 1;
s = 1;
type[id2] = -1;
}
else if (cnt > num) {
type[id1] = -1;
type[id2] = 1;
s = 1;
}
else {
same.pb({id1,id2});
SM.insert({id1,id2});
}
if (P[curnode] != parents[i]) {
insert(curnode,P[curnode]);
// erase(v,parents[i]);
// cnt = ask();
// insert(v,parents[i]);
}
else erased.pb(id[{curnode,parents[i]}]);
curnode = P[curnode];
}while(curnode != parents[i]);
}
for (int i = 1; i < parents.size(); i++) {
erase(v,parents[i]);
}
for (int i : erased) query.insert(i);
num = ask();
vi seen(m+1);
map<int,vector<int> > e;
for (auto i : same) {
e[i.fi].pb(i.se);
e[i.se].pb(i.fi);
}
for (int i = 0; i <= m; i++) {
if (type[i] != 1) continue;
queue<int> q;
if (seen[i]) continue;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
type[v] = 1;
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
for (int i = 0; i <= m; i++) {
if (type[i] != -1) continue;
queue<int> q;
type[i] = -1;
if (seen[i]) continue;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
type[v] = -1;
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
P[v] = p;
if (s == 0 && w[v] == tin[v]) {
for (int i : parents) type[id[{v,i}]] = 1;
if (parents.size())
for (int i = v; i != parents.back();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();
if (num == n-1) {
rlans.clear();
for (int i :query) rlans.pb(i);
}
memset(vis,0,sizeof vis);
vector<int> g = {-1};
// return g;
dfs(0,-1);
if (!rlans.empty()) return rlans;
vi seen(m+1);
map<int,vector<int> > e;
for (auto i : SM) {
e[i.fi].pb(i.se);
e[i.se].pb(i.fi);
}
for (int i = 0; i <= m; i++) {
if (type[i] != 1) continue;
queue<int> q;
if (seen[i]) continue;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
type[v] = 1;
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
for (int i = 0; i <= m; i++) {
if (type[i] != -1) continue;
queue<int> q;
type[i] = -1;
if (seen[i]) continue;
seen[i] = 1;
q.push(i);
while(!q.empty()) {
int v = q.front();
type[v] = -1;
q.pop();
for (int j : e[i]) {
if (seen[j]) continue;
seen[j] = 1;
q.push(j);
}
}
}
// 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:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < parents.size();i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < parents.size(); i++) {
~~^~~~~~~~~~~~~~~~
| # |
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 |
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 |
- |
