#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);
int cn = count_common_roads(r);
for(int i = 0; i < pt; i ++){
int a = u[ r[i] ], b = v[ r[i] ];
if(upper(b, a))
swap(a, b);
int mx = 0, cntg = 0;
vector <int> golds;
for(int j = 0; j < m; j ++){
if(used[j] == 2)
cntg ++;
if(used[j])
continue;
int cnt = 0;
if(upper(b, v[j]))
cnt ++;
if(upper(b, u[j]))
cnt ++;
if(cnt != 1)
continue;
int pre = r[i];
r[i] = j;
int kol = count_common_roads(r);
if(mx < kol){
while(!golds.empty()){
int last = golds.back();
used[last] = 1;
golds.pop_back();
}
mx = kol;
}
if(mx == kol){
golds.emplace_back(j);
} else {
used[j] = 1;
}
}
if(cntg) continue;
for(int j = 0; j < golds.size(); j ++)
used[ golds[j] ] = 2;
}
pt = 0;
for(int i = 0; i < m; i ++){
if(used[i] == 2)
r[pt ++] = i;
}
return r;
}
/***
4 6
0 1
0 2
0 3
1 2
1 3
2 3
1 3 5
****/
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:79:21: warning: unused variable 'pre' [-Wunused-variable]
int pre = r[i];
^~~
simurgh.cpp:97:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < golds.size(); j ++)
~~^~~~~~~~~~~~~~
simurgh.cpp:59:13: warning: unused variable 'cn' [-Wunused-variable]
int cn = count_common_roads(r);
^~
/tmp/cclf4eJu.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/ccRravxm.o:simurgh.cpp:(.text+0x480): first defined here
/tmp/cclf4eJu.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccRravxm.o:simurgh.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
