This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
vector<bool> vis;
vector<vector<int> > adj;
int ans=0;
int DistanceSum(int n,int *a,int *b)
{
adj.resize(n);
map<pair<int,int>,int > m;
for(int x=0;x<n;x++)
m[make_pair(a[x],b[x])]=x;
for(int x=0;x<n;x++)
{
for(int y=0;y<4;y++)
{
if(m.find(make_pair(a[x]+dx[y],b[x]+dy[y]))!=m.end())
{
adj[x].push_back(m[make_pair(a[x]+dx[y],b[x]+dy[y])]);
adj[m[make_pair(a[x]+dx[y],b[x]+dy[y])]].push_back(x);
}
}
}
int tab[n]={0};
for(int x=0;x<n;x++)
{
queue<pair<int,int>> q;
q.push(make_pair(x,0));
vis.assign(n,false);
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
int node=p.first,dis=p.second;
if(!vis[node])
{
vis[node]=true;
tab[x]+=dis;
for(int y=0;y<adj[node].size();y++)
{
int to=adj[node][y];
if(!vis[to])
q.push(make_pair(to,dis+1));
}
}
}
}
ans=0;
for(int x=0;x<n;x++)
ans+=tab[x];
return ans/2;
}
Compilation message (stderr)
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int y=0;y<adj[node].size();y++)
| ~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |