#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"
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;
//////////////
int ask() {
vi v;
for (int i : query) v.pb(i);
int x = 0;//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]) {
query.insert(id[{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]) {
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];
});
for (int i = 1; i < parents.size();i++) {
int cnt = num;
int curnode = v;
insert(v,parents[i]);
P[v] = parents[i-1];
int id2 = id[{v,parents[i]}];
do{
erase(curnode,P[curnode]);
num = ask();
int id1 = id[{curnode,P[curnode]}];
if (cnt < num) {
good.insert(id1);
bad.insert(id2);
}
else if (cnt > num) {
bad.insert(id2);
good.insert(id2);
}
else {
same.pb({id1,id2});
}
cnt = num;
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)
}
if (parents.size() >= 2) erase(v,parents.back());
for (int i : erased) query.insert(i);
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);
}
}
}
if (good.empty() && bad.empty() && w[v] <= tin[v])
for (int i : parents) type[id[{v,i}]] = 1;
for (int i = v; i != parents.back(); i = P[v]) {
type[id[{i,P[i]}]] = 1;
}
w[v] = min(w[v],z);
P[v] = p;
}
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);
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;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < parents.size();i++) {
~~^~~~~~~~~~~~~~~~
simurgh.cpp:110:8: warning: unused variable 'v' [-Wunused-variable]
int v = q.front();
^
simurgh.cpp:125:8: warning: unused variable 'v' [-Wunused-variable]
int v = q.front();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
