#include "simurgh.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 2;
int p[N], sz[N], used[N];
vector <int> g[N];
int f_s(int v){
return (p[v] == v)?v:p[v] = f_s(p[v]);
}
void u_s(int a, int b){
a = f_s(a);
b = f_s(b);
if(a != b){
if(sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
}
int tin[N], tout[N], timer;
void dfs(int v, int pr){
tin[v] = ++ timer;
for(int to : g[v]){
if(to == pr)
continue;
dfs(to, v);
}
tout[v] = timer;
}
bool upper(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<int> r(n - 1);
int m = (int)u.size();
for(int i = 0; i < n; i ++)
p[i] = i, sz[i] = 1;
int pt = 0;
for(int i = 0; i < m; i ++){
if(f_s(u[i]) != f_s(v[i])){
r[pt ++] = i;
u_s(u[i], v[i]);
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
}
dfs(0, 0);
for(int i = 0; i < pt; i ++){
vector <int> ind, rs;
int a = u[ r[i] ], b = v[ r[i] ];
if(upper(b, a))
swap(a, b);
for(int j = 0; j < m; j ++){
int cnt = 0;
if(upper(b, u[j]))
cnt ++;
if(upper(b, v[j]))
cnt ++;
if(cnt == 1)
ind.push_back(j);
}
int mx = 0;
for(int j = 0; j < ind.size(); j ++){
int id = ind[j], pre = r[i];
r[i] = id;
int ret = count_common_roads(r);
mx = max(mx, ret);
r[i] = pre;
rs.emplace_back(ret);
}
for(int j = 0; j < rs.size(); j ++){
if(rs[j] == mx){
used[ ind[j] ] = 2;
}
}
}
pt = 0;
for(int i = 0; i < m; i ++){
if(used[i] == 2)
r[pt ++] = i;
}
return r;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ind.size(); j ++){
~~^~~~~~~~~~~~
simurgh.cpp:81:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < rs.size(); j ++){
~~^~~~~~~~~~~
/tmp/ccJNhZeO.o: In function `count_common_roads(std::vector<int, std::allocator<int> > const&)':
grader.cpp:(.text+0x2e0): multiple definition of `count_common_roads(std::vector<int, std::allocator<int> > const&)'
/tmp/ccW6fvUX.o:simurgh.cpp:(.text+0x480): first defined here
/tmp/ccJNhZeO.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccW6fvUX.o:simurgh.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
