| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387537 | uacoder123 | Ideal city (IOI12_city) | C++14 | 0 ms | 0 KiB |
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 long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
lli n,mod=1000000000;
vector<ii> a(100001),b(100001);
vi r(100001),r1(100001),v(100001),v1(100001),al[100001],al1[100001];
lli ans=0,ans1=0;
unordered_map<lli,lli> m1,m2;
lli dfs(lli node,lli p)
{
lli s=v[node];
for(lli i=0;i<al[node].size();++i)
{
if(al[node][i]!=p)
s=(s+dfs(al[node][i],node))%mod;
}
ans=(ans+((s)*(n-s))%mod)%mod;
return s;
}
lli dfs1(lli node,lli p)
{
lli s=v1[node];
for(lli i=0;i<al1[node].size();++i)
{
if(al1[node][i]!=p)
s=(s+dfs1(al1[node][i],node))%mod;
}
ans1=(ans1+((s)*(n-s))%mod)%mod;
return s;
}
int DistanceSum(lli N, lli *X, lli *Y)
{
n=N;
lli min1=X[0],min2=Y[0];
for(lli i=0;i<n;++i)
{
min1=min(min1,X[i]);
min2=min(min2,Y[i]);
}
for(lli i=0;i<n;++i)
{
a[i]=mp(X[i]-min1,Y[i]-min2);
b[i]=mp(Y[i]-min2,X[i]-min1);
}
sort(a.begin(),a.begin()+n);
sort(b.begin(),b.begin()+n);
lli x1=0,x2=0;
for(lli i=0;i<n;++i)
{
if(i!=0)
{
if(a[i].F==a[i-1].F&&a[i].S-1==a[i-1].S)
r[i]=r[i-1];
else
r[i]=x1++;
}
else
r[i]=x1++;
v[r[i]]++;
if(i!=0)
{
if(b[i].F==b[i-1].F&&b[i].S-1==b[i-1].S)
r1[i]=r1[i-1];
else
r1[i]=x2++;
}
else
r1[i]=x2++;
v1[r1[i]]++;
ii t=mp(a[i].F-1,a[i].S);
lli in;
if(m1.find(t.F*1000000+t.S)!=m1.end())
{
in=m1[t.F*1000000+t.S];
if(al[r[i]].size()&&r[in]==al[r[i]].back())
continue;
al[r[in]].pb(r[i]);
al[r[i]].pb(r[in]);
}
t=mp(b[i].F-1,b[i].S);
if(m2.find(t.F*1000000+t.S)!=m2.end())
{
in=m2[t.F*1000000+t.S];
if(al1[r1[i]].size()&&r1[in]==al1[r1[i]].back())
continue;
al1[r1[in]].pb(r1[i]);
al1[r1[i]].pb(r1[in]);
}
m1[a[i].F*1000000+a[i].S]=i;
m2[b[i].F*1000000+b[i].S]=i;
}
dfs(0,0);
dfs1(0,0);
return (ans+ans1)%mod;
}