| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 483016 | Haidara | Ideal city (IOI12_city) | C++17 | 0 ms | 0 KiB |
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>
#define int long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define FOR(i,n) rep(i,0,n)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define heap(i) priority_queue< i >
using namespace std;
const int inf=1LL<<62LL;
const int mod=1e9+7;
const int maxn=2020;
map<string,int>mp;
int num(pii src)
{
return mp[to_string(src.ff)+":"+to_string(src.ss)];
}
int dx[]{-1,1,0,0};
int dy[]{0,0,1,-1};
int get_dist(pii src)
{
queue<pii>q;
int ans=0;
q.push(src);
v(bool)vis(maxn,0);
v(int)dist(maxn,0);
vis[0]=1;
vis[num(src)]=1;
while(q.size())
{
pii f=q.front();
q.pop();
FOR(i,4)
{
int x=dx[i]+f.ff;
int y=dy[i]+f.ss;
if(!vis[num({x,y})])
{
q.push({x,y});
dist[num({x,y})]=dist[num(f)]+1;
ans+=dist[num({x,y})];
ans%=mod;
vis[num({x,y})]=1;
}
}
}
return ans;
}
int DistanceSum(int n,int *x,int *y)
{
FOR(i,n)
mp[to_string(x[i])+":"+to_string(y[i])]=i+1;
int ans=0;
FOR(i,n)
ans+=get_dist({x[i],y[i]}),ans%=mod;
return ans;
}