oj.uz

Submission #388156

# Submission time Handle Problem Language Result Execution time Memory
388156 2021-04-10T09:54:41 Z uacoder123 Ideal city (IOI12_city) C++14
100 / 100
 127 ms 24076 KB 
#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()))
			{
				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()))
			{
				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

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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 6 ms 11292 KB Output is correct
3 Correct 6 ms 11264 KB Output is correct
4 Correct 6 ms 11212 KB Output is correct
5 Correct 6 ms 11212 KB Output is correct
6 Correct 6 ms 11292 KB Output is correct
7 Correct 7 ms 11212 KB Output is correct
8 Correct 6 ms 11212 KB Output is correct
9 Correct 6 ms 11284 KB Output is correct
10 Correct 8 ms 11212 KB Output is correct
11 Correct 6 ms 11212 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11424 KB Output is correct
2 Correct 7 ms 11340 KB Output is correct
3 Correct 7 ms 11420 KB Output is correct
4 Correct 7 ms 11340 KB Output is correct
5 Correct 8 ms 11468 KB Output is correct
6 Correct 8 ms 11468 KB Output is correct
7 Correct 8 ms 11468 KB Output is correct
8 Correct 8 ms 11468 KB Output is correct
9 Correct 8 ms 11468 KB Output is correct
10 Correct 8 ms 11468 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13388 KB Output is correct
2 Correct 19 ms 13388 KB Output is correct
3 Correct 39 ms 16240 KB Output is correct
4 Correct 40 ms 16188 KB Output is correct
5 Correct 74 ms 21076 KB Output is correct
6 Correct 75 ms 21144 KB Output is correct
7 Correct 79 ms 21316 KB Output is correct
8 Correct 73 ms 20988 KB Output is correct
9 Correct 74 ms 21304 KB Output is correct
10 Correct 78 ms 23572 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13932 KB Output is correct
2 Correct 22 ms 13716 KB Output is correct
3 Correct 61 ms 17512 KB Output is correct
4 Correct 53 ms 17052 KB Output is correct
5 Correct 120 ms 23848 KB Output is correct
6 Correct 90 ms 22280 KB Output is correct
7 Correct 127 ms 24076 KB Output is correct
8 Correct 94 ms 22236 KB Output is correct
9 Correct 83 ms 21916 KB Output is correct
10 Correct 83 ms 21832 KB Output is correct