#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace TRUNG{
const ll MAXN = 510;
ll n,m;
ll ans[MAXN*MAXN];
vector <pll> g[MAXN];
bool sus[MAXN*MAXN];
ll in[MAXN],out[MAXN];
ll timeDFS;
vector <pll> a;
ll cnt_query;
void dfs(ll u,ll p){
in[u] = ++timeDFS;
for (auto tmp:g[u]){
ll v = tmp.fi,id = tmp.se;
if (v==p)continue;
dfs(v,u);
}
out[u] = timeDFS;
}
bool sus_edge(ll i,ll j){
ll x = a[i].fi;
if (in[a[i].se] > in[x])x = a[i].se;
// cout<<i<<' '<<j<<' '<<x<<endl;
if ((in[x] <= in[a[j].fi] && in[a[j].fi] <= out[x])+(in[x] <= in[a[j].se] && in[a[j].se] <= out[x])==1)return 1;
return 0;
}
namespace DSU{
ll dsu[MAXN];
void init(){
memset(dsu,-1,sizeof dsu);
}
ll f(ll x){
if (dsu[x] < 0)return x;
return (dsu[x] = f(dsu[x]));
}
void join(ll x,ll y){
x = f(x),y = f(y);
if (x!=y){
if (dsu[x] > dsu[y])swap(x,y);
dsu[x] += dsu[y];
dsu[y] = x;
}
}
}
bitset <MAXN> bs[MAXN];
ll ind[MAXN][MAXN];
vector <ll> tree,extra;
ll superior_count(vector <ll> all){
DSU::init();
for (auto x:all){
DSU::join(a[x].fi,a[x].se);
}
ll res = 0;
for (auto x:tree){
if (DSU::f(a[x].fi) != DSU::f(a[x].se)){
DSU::join(a[x].fi,a[x].se);
all.push_back(x);
res-=ans[x];
}
}
assert(++cnt_query<=8000);
res += count_common_roads(all);
return res;
}
void solve(vector <ll> all,ll k){
if (k==0)return;
if (sz(all) == 1){
ans[all[0]] = k;
return;
}
ll mid = sz(all) / 2;
vector <ll> L,R;
for (ll i = 0;i < sz(all);i ++){
if (i < mid)L.push_back(all[i]);
else R.push_back(all[i]);
}
ll cnt_L = superior_count(L);
solve(L,cnt_L);
solve(R,k-cnt_L);
}
}
std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
using namespace TRUNG;
memset(ans,-1,sizeof ans);
ll m = sz(U),n=N ;
a.resize(m);
for (ll i = 0;i < m;i ++)a[i] = MP(U[i],V[i]);
DSU::init();
for (ll i = 0;i < m;i ++){
if (DSU::f(a[i].fi) != DSU::f(a[i].se)){sus[i] = 1;tree.push_back(i);}
DSU::join(a[i].fi,a[i].se);
}
DSU::init();
for (ll i = 0;i < m;i ++){
if (sus[i])continue;
if (DSU::f(a[i].fi) != DSU::f(a[i].se))extra.push_back(i);
DSU::join(a[i].fi,a[i].se);
}
for (auto id:tree){
g[a[id].fi].push_back(MP(a[id].se,id));
g[a[id].se].push_back(MP(a[id].fi,id));
}
dfs(0,0);
// cout<<in[4]<<' '<<out[4]<<' '<<in[1]<<' '<<out[1]<<endl;
// for (auto x:tree)cout<<x<<' ';
// cout<<'\n';
// for (auto x:extra)cout<<x<<' ';
// cout<<'\n';
// cout<<sus_edge(4,7)<<endl;
ll cur = count_common_roads(tree);
assert(++cnt_query<=8000);
for (auto id:tree){
// cout<<id<<endl;
if (ans[id] != -1)continue;
for (auto x:extra){
if (sus_edge(id,x)){
// cout<<"WOW "<<x<<' '<<id<<endl;
auto cal = [&](ll y){
vector <ll> tmp;
for (ll i = 0;i < 1000;i ++)tree.push_back(69);
for (ll i = 0;i < 1000;i ++)tree.pop_back();
tree.push_back(x);
for (auto sss:tree)if (sss != y)tmp.push_back(sss);
tree.pop_back();
assert(++cnt_query<=8000);
// cout<<"CAL "<<y<<": ";
// for (auto z:tmp)cout<<z<<' ';
// cout<<endl;
ll res = count_common_roads(tmp);
// cout<<"VAL "<<res<<endl;
return res;
};
vector <ll> cycle;
for (auto y:tree){
if (sus_edge(y,x)){
cycle.push_back(y);
}
}
// for (auto y:cycle)cout<<y<<' ';
// cout<<endl;
ll sum = -1;
if (ans[x] != -1)sum = ans[x] + cur;
for (auto y:cycle){
if (ans[y] != -1 && sum == -1){
sum = cal(y) + ans[y];
break;
}
}
if (sum==-1){
vector <ll> com(sz(cycle));
for (ll j = 0;j < sz(cycle);j ++){
com[j] = cal(cycle[j]);
if (com[j] < cur)sum = cur;
if (com[j] > cur)sum = cur+1;
// cout<<cycle[j]<<' '<<com[j]<<endl;
}
if (sum == -1)sum = cur;
for (ll j = 0;j < sz(cycle);j ++){
ans[cycle[j]] = sum - com[j];
}
ans[x] = sum - cur;
}
else{
for (auto y:cycle)if (ans[y] == -1){
ans[y] = sum - cal(y);
}
ans[x] = sum - cur;
}
break;
}
}
if (ans[id] == -1)ans[id] = 1;
}
// for (ll j = 0;j < m;j ++)cout<<ans[j]<<' ';
// cout<<endl;
for (ll j = 0;j < m;j ++){
pll x = a[j];
ind[x.fi][x.se]=ind[x.se][x.fi]=j;
if (ans[j] == -1)bs[x.fi][x.se] = bs[x.se][x.fi] = 1;
}
while (true){
bitset <MAXN> rem;
rem.set();
bitset <MAXN> tmp;
vector <ll> cur;
for (ll i = 0;i < n;i ++){
if (rem[i]){
queue <ll> q;
q.push(i);
rem[i] = 0;
while (!q.empty()){
ll u = q.front();
q.pop();
tmp = rem & bs[u];
for (ll v = tmp._Find_first();v < n;v = tmp._Find_next(v)){
cur.push_back(ind[u][v]);
bs[u][v] = bs[v][u] = 0;
q.push(v);
rem[v] = 0;
}
}
}
}
if (!sz(cur))break;
// cout<<sz(cur)<<' '<<cur[0]<<endl;
solve(cur,superior_count(cur));
}
vector <ll> r;
for (ll i = 0;i < m;i ++)if (ans[i]==1)r.push_back(i);
// assert(cnt_query<=8000);
// count_common_roads
return r;
}
Compilation message
simurgh.cpp: In function 'void TRUNG::dfs(ll, ll)':
simurgh.cpp:26:27: warning: unused variable 'id' [-Wunused-variable]
26 | ll v = tmp.fi,id = tmp.se;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
correct |
| 2 |
Runtime error |
2 ms |
4956 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
