#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=505;
int n,m,mark[N],comp[N],cnt[N],pdge[N],Max[N];
vector<int> edge,ans;
vector<pair<int,int>> g[N];
void dfs(int u,int col){
comp[u]=col;
for(auto [v,id] : g[u]){
if(comp[v]) continue ;
edge.pb(id);
dfs(v,col);
}
}
int ask(vector<int> &vec){
return count_common_roads(vec);
}
vector<int> find_roads(int _n,vector<int> u,vector<int> v){
vector<int> ans;
n=_n,m=u.size();
f(i,0,m) g[u[i]].pb({v[i],i}),g[v[i]].pb({u[i],i});
queue<int> q;
q.push(0);
mark[0]=1;
while(q.size()){
edge.clear();
int u=q.front();
q.pop();
f(i,0,n) comp[i]=Max[i]=cnt[i]=0; comp[u]=1;
int col=0;
for(auto [v,id] : g[u]){
if(comp[v]==0){
col++;
dfs(v,col);
pdge[col]=id;
edge.pb(id);
}
}
int res=ask(edge);
for(auto [v,id] : g[u]){
if(pdge[comp[v]]==id){
cnt[v]=res;
}
}
for(auto [v,id] : g[u]){
if(mark[v] || pdge[comp[v]]==id) continue ;
vector<int> vec;
for(auto x : edge){
if(x!=pdge[comp[v]])
vec.pb(x);
}
vec.pb(id);
cnt[v]=ask(vec);
}
for(auto [v,id] : g[u]){
maxm(Max[comp[v]],cnt[v]);
}
for(auto [v,id] : g[u]){
if(cnt[v]>0 && Max[comp[v]]==cnt[v] && mark[v]==0){
mark[v]=1;
q.push(v);
ans.pb(id);
}
}
}
//dbgv(ans);
return ans;
}
Compilation message
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:32:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for(auto [v,id] : g[u]){
| ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:9:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
| ^~~
simurgh.cpp:52:3: note: in expansion of macro 'f'
52 | f(i,0,n) comp[i]=Max[i]=cnt[i]=0; comp[u]=1;
| ^
simurgh.cpp:52:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
52 | f(i,0,n) comp[i]=Max[i]=cnt[i]=0; comp[u]=1;
| ^~~~
simurgh.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for(auto [v,id] : g[u]){
| ^
simurgh.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto [v,id] : g[u]){
| ^
simurgh.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for(auto [v,id] : g[u]){
| ^
simurgh.cpp:78:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | for(auto [v,id] : g[u]){
| ^
simurgh.cpp:81:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [v,id] : g[u]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
320 KB |
correct |
| 3 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
320 KB |
correct |
| 3 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
320 KB |
correct |
| 3 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
1 ms |
320 KB |
correct |
| 3 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
