Submission #333630

#	Time	Username	Problem	Language	Result	Execution time	Memory
333630		keta_tsimakuridze	Ideal city (IOI12_city)	C++14	100 / 100	202 ms	28648 KiB

city

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int N=1e5+5;
const int mod=1e9;
ll s[N],ans,n,cnt,X[N],Y[N];
pair<ll,ll>a[N];
map<pair<ll,ll>,ll>mp;
vector<ll>V[N],v[N];
void dfs(int u,int p){
	s[u]=v[u].back()-v[u][0]+1; s[u]%=mod;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p){ 
			dfs(V[u][i],u);
			s[u]+=s[V[u][i]];
			s[u]%=mod;
		}
	}
	ans+=s[u]*(n-s[u])%mod;//cout<<u<<" -- "<<s[u]<<endl;
	ans%=mod;
}
void Tree(){
	//cout<<"+"<<endl;
	 for(int i=0;i<n;i++){
  	if(!i || a[i].f!=a[i-1].f || a[i].s!=a[i-1].s+1){
  		cnt++;  
  	    //cout<<a[i].f<<" "<<a[i].s<<"_"<<cnt<<endl;
  	
	  }	mp[{a[i].f,a[i].s}]=cnt;v[cnt].push_back(a[i].s);
  }
  for(int i=0;i<n;i++){
  	if(mp[{a[i].f+1,a[i].s}]){
  		int cc=mp[{a[i].f+1,a[i].s}]; 
  		if(V[mp[{a[i].f,a[i].s}]].size()==0 || V[mp[{a[i].f,a[i].s}]].back()!=cc){
  		V[mp[{a[i].f,a[i].s}]].push_back(cc);
		V[cc].push_back(mp[{a[i].f,a[i].s}]);	
		}
	  }
  }
  dfs(1,0);
}
ll DistanceSum(int N, int *X, int *Y) {
  for(int i=0;i<N;i++){
  	a[i]={X[i],Y[i]};
  } n=N;
  sort(a,a+N);
  Tree();
  for(int i=1;i<=cnt;i++)
    v[i].clear(),V[i].clear();
	cnt=0;
  for(int i=0;i<N;i++)
  mp[{a[i].f,a[i].s}]=0,swap(a[i].f,a[i].s); 
  sort(a,a+N);
  Tree(); 
  return ans;
}

Compilation message (stderr)

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

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