oj.uz

Submission #333630

# Submission time Handle Problem Language Result Execution time Memory
333630 2020-12-07T09:21:16 Z keta_tsimakuridze Ideal city (IOI12_city) C++14
100 / 100
 202 ms 28648 KB 
#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

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

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5228 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 6 ms 5356 KB Output is correct
4 Correct 6 ms 5356 KB Output is correct
5 Correct 7 ms 5484 KB Output is correct
6 Correct 7 ms 5484 KB Output is correct
7 Correct 7 ms 5504 KB Output is correct
8 Correct 7 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 6 ms 5356 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7660 KB Output is correct
2 Correct 33 ms 8684 KB Output is correct
3 Correct 73 ms 11148 KB Output is correct
4 Correct 77 ms 13676 KB Output is correct
5 Correct 139 ms 15596 KB Output is correct
6 Correct 155 ms 23168 KB Output is correct
7 Correct 156 ms 22968 KB Output is correct
8 Correct 151 ms 15980 KB Output is correct
9 Correct 160 ms 23020 KB Output is correct
10 Correct 197 ms 28648 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9836 KB Output is correct
2 Correct 37 ms 9324 KB Output is correct
3 Correct 95 ms 16492 KB Output is correct
4 Correct 94 ms 14956 KB Output is correct
5 Correct 191 ms 27596 KB Output is correct
6 Correct 169 ms 23916 KB Output is correct
7 Correct 202 ms 27652 KB Output is correct
8 Correct 172 ms 24812 KB Output is correct
9 Correct 156 ms 18412 KB Output is correct
10 Correct 161 ms 21740 KB Output is correct