#include "island.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int n,m;
vector<ii> edges;
vi ss[301111];
typedef bitset<1011> b100;
b100 las[101111];
struct DSU
{
int S;
struct node
{
int p; int las;
};
vector<node> dsu;
DSU(int n=0)
{
S = n;
for(int i = 0; i < n; i++)
{
node tmp;
tmp.p = i; tmp.las = -1;
dsu.pb(tmp);
}
}
void reset(int n)
{
dsu.clear();
S = n;
for(int i = 0; i < n; i++)
{
node tmp;
tmp.p = i; tmp.las = -1;
dsu.pb(tmp);
}
}
int rt(int u)
{
if(dsu[u].p == u) return u;
dsu[u].p = rt(dsu[u].p);
return dsu[u].p;
}
void merge(int u, int v)
{
u = rt(u); v = rt(v);
if(u == v) return ;
if(ss[u].size()<ss[v].size()) swap(u,v);
dsu[v].p = u; dsu[u].las = v;
for(int x:ss[v])
{
ss[u].pb(x);
}
ss[v].clear();
for(int r:ss[u])
{
las[v].set(r,1);
}
}
bool sameset(int u, int v)
{
if(rt(u) == rt(v)) return true;
return false;
}
};
struct DSUSimple
{
int S;
struct node
{
int p; int s;
};
vector<node> dsu;
DSUSimple(int n=0)
{
S = n;
for(int i = 0; i < n; i++)
{
node tmp;
tmp.p = i; tmp.s=0;
dsu.pb(tmp);
}
}
void reset(int n)
{
dsu.clear();
S = n;
for(int i = 0; i < n; i++)
{
node tmp;
tmp.p = i; tmp.s=0;
dsu.pb(tmp);
}
}
int rt(int u)
{
if(dsu[u].p == u) return u;
dsu[u].p = rt(dsu[u].p);
return dsu[u].p;
}
void merge(int u, int v)
{
u = rt(u); v = rt(v);
if(u == v) return ;
if(rand()&1) swap(u,v);
dsu[v].p = u; dsu[u].s|=dsu[v].s;
}
bool sameset(int u, int v)
{
if(rt(u) == rt(v)) return true;
return false;
}
};
const int C = 450;
const int M = 300111;
DSU ds[M/C+10];
DSUSimple ds2[M/C+10];
int ini[111111];
int st[333333];
int ma[333333];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E)
{
n = F.size();
m = S.size();
for(int i=0;i<n;i++) ini[i]=F[i];
for(int i=0;i<m;i++)
{
edges.pb({S[i],E[i]});
}
reverse(edges.begin(),edges.end());
for(int i=0;i<M/C+10;i++)
{
ds[i].reset(n); ds2[i].reset(K);
}
for(int i=0;i<n;i++)
{
ss[i].pb(F[i]);
}
for(int i=0;i<m;i++)
{
if(i%C==0)
{
int cur=i/C;
for(int j=0;j<n;j++)
{
if(ds[cur].rt(j)==j)
{
if(ss[j].size()>0)
{
int in = *(ss[j].begin());
for(int v:ss[j])
{
ds2[cur].merge(in,v);
//cerr<<"DS2 "<<cur<<" MERGE "<<in<<' '<<v<<'\n';
}
}
}
}
ds[i/C+1]=ds[i/C];
}
int u=edges[i].fi; int v=edges[i].se;
ds[i/C+1].merge(u,v);
}
int cur=(m-1)/C+1;
for(int j=0;j<n;j++)
{
if(ds[cur].rt(j)==j)
{
if(ss[j].size()>0)
{
int in = *(ss[j].begin());
for(int v:ss[j])
{
ds2[cur].merge(in,v);
//cerr<<"DS2 "<<cur<<" MERGE "<<in<<' '<<v<<'\n';
}
}
}
}
memset(ma,-1,sizeof(ma));
}
int Separate(int A, int B)
{
int id=0;
for(int i=0;i<M/C+10;i++)
{
if(ds2[i].sameset(A,B))
{
id=i-1; break;
}
}
//start from ds[id]
//until curm-1 A and B arent connected
int curm = C*id;
int cur=-1;
vi vv;
for(int i=curm;i<min(C*(id+1),m);i++)
{
int u=edges[i].fi; int v=edges[i].se;
u=ds[id].rt(u); v=ds[id].rt(v);
if(u==v) continue;
if(ma[u]==-1)
{
vv.pb(u); ma[u]=++cur;
}
if(ma[v]==-1)
{
vv.pb(v); ma[v]=++cur;
}
}
DSUSimple simple(cur+1);
for(int u:vv)
{
if(ds[id].dsu[u].las==-1)
{
if(ini[u]==A) st[u]|=1;
if(ini[u]==B) st[u]|=2;
}
else
{
int v=ds[id].dsu[u].las;
if(las[v][A]) st[u]|=1;
if(las[v][B]) st[u]|=2;
}
//if(binary_search(FF[id][A].begin(),FF[id][A].end(),u)) st[u]|=1;
//if(binary_search(FF[id][B].begin(),FF[id][B].end(),u)) st[u]|=2;
//cerr<<u<<' '<<x.se<<' '<<st[u]<<endl;
simple.dsu[ma[u]].s=st[u];
//cerr<<x.se<<' '<<st[u]<<endl;
}
int ans = 0;
for(int i=curm;i<min(C*(id+1),m);i++)
{
int u=edges[i].fi; int v=edges[i].se;
u=ds[id].rt(u); v=ds[id].rt(v);
if(u==v) continue;
int U = ma[u];
int V = ma[v];
//cerr<<"MERGE: "<<U<<' '<<V<<'\n';
simple.merge(U,V);
U=simple.rt(U);
if(simple.dsu[U].s==3)
{
ans=i; break;
}
}
for(int x:vv)
{
st[x]=0; ma[x]=-1;
}
return m-ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3006 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
8960 KB |
Output is correct |
| 2 |
Correct |
13 ms |
8856 KB |
Output is correct |
| 3 |
Execution timed out |
5099 ms |
524288 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
8960 KB |
Output is correct |
| 2 |
Correct |
13 ms |
8856 KB |
Output is correct |
| 3 |
Runtime error |
3006 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
