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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int par[1501],r[1501];
set<ii> s[1501];
int find(int x)
{
if(par[x]==par[par[x]]) return par[x];
par[x]=find(par[x]); return par[x];
}
void m(int a,int b)
{
for(auto it:s[b])
{
s[it.F].erase(mp(b,it.S));
auto it1=s[a].lower_bound(mp(it.F,-1));
s[(*it1).F].erase(mp(a,(*it1).S));
ii f=mp(it.F,it.S+(*it1).S);
s[a].erase(it1);
s[a].insert(f);
s[f.F].insert(mp(a,f.S));
}
}
void mer(int a,int b)
{
if(r[a]>=r[b])
{
par[b]=a;
m(a,b);
if(r[a]==r[b])
r[a]++;
}
else
{
m(b,a);
par[a]=b;
}
}
void initialize(int n)
{
for(int i=0;i<n;++i)
{
par[i]=i;
r[i]=1;
for(int j=i+1;j<n;++j)
{
s[i].insert(mp(j,1));
s[j].insert(mp(i,1));
}
}
}
int hasEdge(int u, int v)
{
int pu=find(u),pv=find(v);
if(pu==pv)
return 0;
ii f=(*s[pu].lower_bound(mp(pv,-1)));
if(f.S>1)
{
s[pu].erase(mp(pv,f.S));
s[pv].erase(mp(pu,f.S));
s[pu].insert(mp(pv,f.S-1));
s[pv].insert(mp(pu,f.S-1));
return 0;
}
s[pu].erase(mp(pv,1));
s[pv].erase(mp(pu,1));
mer(pu,pv);
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |