Submission #69625

#	Time	Username	Problem	Language	Result	Execution time	Memory
69625		Abelyan	Ideal city (IOI12_city)	C++17	32 / 100	149 ms	1884 KiB

city

#include <bits/stdc++.h>
#define LL long long
#define pll pair<LL,LL>
using namespace std;

const int  MOD = 1000000000;

struct ci{
    LL x,y;
    int nea[4]={-1,-1,-1,-1};
}inf[2222];
 
LL n,sum;
LL x[2222],y[2222];
map<pll,int> mp;
 
queue<int> qi,qd;
bool used[2222];
 
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
 
void bfs(int v,int d){
    qi.push(v);
    qd.push(d);
    used[v]=true;
    while(!qi.empty()){
        int pi=qi.front(); qi.pop();
        int pd=qd.front(); qd.pop();
        sum=(sum+pd)%(MOD*2);
 
        for(int i=0;i<4;i++){
            if(inf[pi].nea[i]!=-1 && !used[inf[pi].nea[i]]){
                qi.push(inf[pi].nea[i]);
                qd.push(pd+1);
                used[inf[pi].nea[i]]=1;
            }
        }
    }
}
 
int DistanceSum(int N,int *X,int *Y){
    n=N;
    for(int i=0;i<N;i++) x[i]=X[i];
    for(int i=0;i<N;i++) y[i]=Y[i];
 
    for(int i=0;i<n;i++) mp.insert({{x[i],y[i]},i});
    for(int i=0;i<n;i++){
        inf[i].x=x[i];
        inf[i].y=y[i];
        for(int j=0;j<4;j++){
            int nx=x[i]+dx[j];
            int ny=y[i]+dy[j];
 
            map<pll,int>::iterator it=mp.find({nx,ny});
            if(it!=mp.end()) inf[i].nea[j]=it->second;
        }
    }
 
    if(n<=2000){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) used[j]=0;
            bfs(i,0);
        }
 
        return sum/2;
    }
 
    return 0;
}

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