Submission #483021

#	Time	Username	Problem	Language	Result	Execution time	Memory
483021		Haidara	Ideal city (IOI12_city)	C++17	0 / 100	1086 ms	4044 KiB

city

#include<bits/stdc++.h>
#define ll 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 ll inf=1LL<<62LL;
const ll mod=1000000000;
const ll 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};
ll get_dist(pii src)
{
    queue<pii>q;
    ll ans=0;
    q.push(src);
    v(bool)vis(maxn,0);
    v(ll)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;
    ll ans=0;
    FOR(i,n)
        ans+=get_dist({x[i],y[i]}),ans%=mod;
    return ans;
}

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