Submission #387538

#	Time	Username	Problem	Language	Result	Execution time	Memory
387538		uacoder123	Ideal city (IOI12_city)	C++14	0 / 100	27 ms	13676 KiB

city

#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(int N, int *X, int *Y) 
{
	n=N;
	lli min1=X[0],min2=Y[0];
	for(lli i=0;i<n;++i)
	{
		min1=min(min1,X[i]*1LL);
		min2=min(min2,Y[i]*1LL);
	}
	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;
}

Compilation message (stderr)

city.cpp: In function 'lli dfs(lli, lli)':
city.cpp:27:15: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(lli i=0;i<al[node].size();++i)
      |              ~^~~~~~~~~~~~~~~~
city.cpp: In function 'lli dfs1(lli, lli)':
city.cpp:38:15: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(lli i=0;i<al1[node].size();++i)
      |              ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45