Submission #383199

#	Time	Username	Problem	Language	Result	Execution time	Memory
383199		kshitij_sodani	Ideal city (IOI12_city)	C++14	100 / 100	343 ms	21724 KiB

city

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

set<int> adj[100001];
const llo mod=1e9;
llo ans=0;
llo ss[100001];

llo tt[100001];
llo nn;
void dfs(int no,int par=-1){
	ss[no]=tt[no];
	for(auto j:adj[no]){
		if(j!=par){
			//cout<<no<<":"<<j<<endl;
			dfs(j,no);
			ans+=(nn-ss[j])*ss[j];
			ans%=mod;
			ss[no]+=ss[j];
		}
	}
}
void solve(vector<int> x ,vector<int> y){
	int n=x.size();
	nn=n;
	//cout<<11<<endl;
	vector<pair<int,int>> ss;
	for(int i=0;i<n;i++){
		ss.pb({x[i],y[i]});
	}
	sort(ss.begin(),ss.end());
	int ind=0;
	int cot=-1;
	map<pair<int,int>,int> yy;
	for(int i=0;i<n;i++){
		adj[i].clear();
		tt[i]=0;
	}
	while(ind<ss.size()){
		cot++;
		pair<int,int> cur=ss[ind];
		while(ind<ss.size()){
			if(ss[ind].a!=cur.a){
				break;
			}
			if(ss[ind].b==cur.b){
				tt[cot]++;
				yy[ss[ind]]=cot;
				cur.b+=1;
				ind+=1;
			}
			else{
				break;
			}
		}
	}

	for(int i=0;i<n;i++){
		vector<int> zz={1,-1};
		vector<int> zz2={0,0};
		for(int j=0;j<2;j++){
			pair<int,int> ne={ss[i].a+zz[j],ss[i].b+zz2[j]};
			if(yy.find(ne)!=yy.end()){
				adj[yy[ss[i]]].insert(yy[ne]);
				adj[yy[ne]].insert(yy[ss[i]]);
			}
		}
	}
	dfs(0);
	

}
int DistanceSum(int n, int *xx, int *yy) {

	

	//sort(xx.begin(),ss.end());
	vector<int> x;
	vector<int> y;
	for(int i=0;i<n;i++){
		x.pb(xx[i]);
		y.pb(yy[i]);
	}
	solve(x,y);
	solve(y,x);



 	return (int)ans;

}

Compilation message (stderr)

city.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
city.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  while(ind<ss.size()){
      |        ~~~^~~~~~~~~~
city.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while(ind<ss.size()){
      |         ~~~^~~~~~~~~~

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