| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 879133 |
2023-11-26T12:08:40 Z |
YongXin |
Ideal city (IOI12_city) |
C++14 |
|
1000 ms |
5760 KB |
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
int DistanceSum(int n,int*X,int*Y){
ll x=0,y=0,maxx=0,maxy=0,minx=9e18,miny=9e18,r=0;
vector<pll>vx,vy;
queue<pll>q;
pll a[n];
pair<int,int>temp[n];
for(ll i=0;i<n;++i){
temp[i]=make_pair(X[i],Y[i]);
maxx=max(maxx,(ll)temp[i].first);
maxy=max(maxy,(ll)temp[i].second);
minx=min(minx,(ll)temp[i].first);
miny=min(miny,(ll)temp[i].second);
}
sort(temp,temp+n);
maxx-=minx-1;
maxy-=miny-1;
pll arr[maxy][maxx];
memset(arr,-1,16*maxy*maxx);
for(ll i=0;i<n;++i){
temp[i].first-=minx;
temp[i].second-=miny;
if(temp[i].first!=0&&arr[temp[i].first-1][temp[i].second].first!=-1)a[i].first=arr[temp[i].first-1][temp[i].second].first;
else{
a[i].first=x;
++x;
}
if(temp[i].second!=0&&arr[temp[i].first][temp[i].second-1].second!=-1)a[i].second=arr[temp[i].first][temp[i].second-1].second;
else{
a[i].second=y;
++y;
}
arr[temp[i].first][temp[i].second]=a[i];
if(temp[i].first!=0&&arr[temp[i].first-1][temp[i].second].first!=-1)vy.push_back(make_pair(arr[temp[i].first-1][temp[i].second].second,a[i].second));
if(temp[i].second!=0&&arr[temp[i].first][temp[i].second-1].second!=-1)vx.push_back(make_pair(arr[temp[i].first][temp[i].second-1].first,a[i].first));
}
ll nx[x],ny[y];
bool visitx[x],visity[y];
vector<ll>adjx[x],adjy[y];
memset(nx,0,8*x);
memset(ny,0,8*y);
for(ll i=0;i<n;++i){
++nx[a[i].first];
++ny[a[i].second];
}
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
sort(vy.begin(),vy.end());
vy.erase(unique(vy.begin(),vy.end()),vy.end());
for(ll i=0;i<vx.size();++i){
adjx[vx[i].first].push_back(vx[i].second);
adjx[vx[i].second].push_back(vx[i].first);
}
for(ll i=0;i<vy.size();++i){
adjy[vy[i].first].push_back(vy[i].second);
adjy[vy[i].second].push_back(vy[i].first);
}
for(ll i=0;i<x;++i){
memset(visitx,-1,x);
q.push(make_pair(i,0));
while(!q.empty()){
if(visitx[q.front().first]){
if(q.front().first>i)r+=q.front().second*nx[i]*nx[q.front().first];
visitx[q.front().first]=false;
for(ll j=0;j<adjx[q.front().first].size();++j)q.push(make_pair(adjx[q.front().first][j],q.front().second+1));
}
q.pop();
}
}
for(ll i=0;i<y;++i){
memset(visity,-1,y);
q.push(make_pair(i,0));
while(!q.empty()){
if(visity[q.front().first]){
if(q.front().first>i)r+=q.front().second*ny[i]*ny[q.front().first];
visity[q.front().first]=false;
for(ll j=0;j<adjy[q.front().first].size();++j)q.push(make_pair(adjy[q.front().first][j],q.front().second+1));
}
q.pop();
}
}
return(int)(r%(int)1e9);
}
Compilation message
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(ll i=0;i<vx.size();++i){
| ~^~~~~~~~~~
city.cpp:57:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(ll i=0;i<vy.size();++i){
| ~^~~~~~~~~~
city.cpp:68:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(ll j=0;j<adjx[q.front().first].size();++j)q.push(make_pair(adjx[q.front().first][j],q.front().second+1));
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:80:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(ll j=0;j<adjy[q.front().first].size();++j)q.push(make_pair(adjy[q.front().first][j],q.front().second+1));
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5760 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
5008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
