This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
const int N=5e2+10;
typedef pair<int,int> pii;
struct dsu{
int p[N],sz[N];
void make(int v){
p[v]=v;
sz[v]=1;
}
void init(){
for(int i=0;i<N;i++)
make(i);
}
int get(int v){
return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b){
a=get(a),b=get(b);
if(a==b) return 0;
if(sz[a]>sz[b]) swap(a,b);
p[a]=b;sz[b]+=sz[a];
return 1;
}
}ds;
vec<array<int,4>> goods;
vec<int> ones;
bool used[N*N];
int pr[N];
int ids[N];
bool ema[N*N];
int clr[N*N];
int u[N];
vec<array<int,3>> backt;
vec<array<int,3>> inc;
vec<pii> g[N];
int get(vec<array<int,3>> vc){
ds.init();
vec<int>asks;
for(auto &z : vc){
// assert(ds.mg(z[0],z[1]));
if(!ds.mg(z[0],z[1])){
exit(0);
}
asks.pb(z[2]);
}
int hv=0;
for(auto &z : goods){
if(ds.mg(z[0],z[1])){
hv-=z[3];
asks.pb(z[2]);
// cout<<"DELETE "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
}
}
hv+=count_common_roads(asks);
// if(hv<0){
// cout<<"EBLAN "<<endl;
// for(auto &zt : asks){
// cout<<zt<<endl;
// }
// cout<<endl;
// }
return hv;
}
void rec(vec<array<int,3>> vc, int have){
if(!have || sz(vc)==0) return;
if(sz(vc)==1){
goods.pb({vc[0][0],vc[0][1],vc[0][2],1});
return;
}
ds.init();
vec<array<int,3>> lft,rgt;
for(int i=0;i<sz(vc)/2;i++)
lft.pb(vc[i]);
for(int i=sz(lft);i<sz(vc);i++)
rgt.pb(vc[i]);
// for(auto &z : vc)
// cout<<z[0]<<' '<<z[1]<<endl;
// cout<<"HAVE "<<have<<endl;
int hv=get(lft);
rec(lft,hv);
rec(rgt,have-hv);
}
void dfs(int v,int p){
u[v]=1;
for(auto &z : g[v]){
if(z.f==p || u[z.f]==2) continue;
if(u[z.f]==1){
backt.pb({v,z.f,z.s});
}
else{
pr[z.f]=v;
ids[z.f]=z.s;
inc.pb({v,z.f,z.s});
dfs(z.f,v);
}
}
u[v]=2;
}
vec<int> find_roads(int n, vec<int> v,vec<int> u){
int m=sz(v);
for(int i=0;i<m;i++){
g[v[i]].pb({u[i],i});
g[u[i]].pb({v[i],i});
}
dfs(0,0);
int ostov=get(inc);
for(auto &z : backt){
int v=z[0];
vec<array<int,3>>idk;
int iam1=-1;
if(z[2]==48){
cout<<"IMG "<<endl;
z[2]=48;
}
while(v!=z[1]){
if(!used[ids[v]]){
vec<array<int,3>> toask;
for(auto &zt : inc){
if(zt[2]!=ids[v]) toask.pb(zt);
}
toask.pb(z);
int me=get(toask);
if(me==ostov){
idk.pb({v,pr[v],ids[v]});
}
else{
if(me>ostov){
goods.pb({v,pr[v],ids[v],0});
iam1=1;
clr[ids[v]]=0;
clr[z[2]]=1;
goods.pb({z[0],z[1],z[2],1});
}
else{
goods.pb({v,pr[v],ids[v],1});
iam1=0;
clr[ids[v]]=1;
clr[z[2]]=0;
goods.pb({z[0],z[1],z[2],0});
}
used[z[2]]=1;
used[ids[v]]=1;
}
}
v=pr[v];
}
if(sz(idk)){
if(iam1==-1){
v=z[0];
while(v!=z[1]){
int j=ids[v];
if(used[j]){
int cv=clr[j];
vec<array<int,3>> toask;
for(auto &zt : inc){
if(zt[2]!=ids[v]) toask.pb(zt);
}
toask.pb(z);
int me=get(toask);
if(me==ostov){
iam1=cv;
clr[z[2]]=cv;
}
else{
if(me<ostov){
assert(cv);
iam1=0;
clr[z[2]]=0;
}
else{
assert(!cv);
iam1=1;
clr[z[2]]=1;
}
}
break;
}
v=pr[v];
}
if(iam1==-1){
iam1=0;
}
}
goods.pb({z[0],z[1],z[2],clr[z[2]]});
used[z[2]]=1;
for(auto &z : idk){
goods.pb({z[0],z[1],z[2],iam1});
clr[z[2]]=iam1;
// cout<<z[2]<<endl;
used[z[2]]=1;
}
}
// cout<<"ALWAYS "<<z[2]<<endl<<endl;
// for(auto &q : goods){
// cout<<q[2]<<endl;
// }
// cout<<endl;
}
// for(auto &z : goods){
// cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
// }
// exit(0);
for(auto &z : inc){
if(!used[z[2]]){
goods.pb({z[0],z[1],z[2],1});
used[z[2]]=1;
}
// cout<<"INC "<<z[0]<<' '<<z[1]<<endl;
}
sort(all(goods));goods.erase(unique(all(goods)),goods.end());
// for(auto &z : goods){
// cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
// }
// return ones;
for(int i=0;i<n;i++){
vec<array<int,3>>kekw;
for(auto &z : g[i]){
if(!used[z.s]){
kekw.pb({i,z.f,z.s});
used[z.s]=1;
}
}
if(sz(kekw)){
rec(kekw,get(kekw));
}
}
for(auto &z : goods){
if(z[3]==1)
ones.pb(z[2]);
}
return ones;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
6 7
0 1
1 2
2 3
2 4
4 5
0 2
1 5
0 2 4 5 6
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |