Submission #1243815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243815		simplemind_31	Ideal city (IOI12_city)	C++20	32 / 100	147 ms	1348 KiB

city

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
vector<pair<int,int>> puntos;
int minix=2e9,miniy=2e9;
int dist[2002][2002];
bool existe[2002][2002];
ll tot;
vector<pair<int,int>> bound_nivel;
vector<ll> res_temp,res_abs;
vector<ll> psum_nivel;
ll sumar(ll x,ll y){
  if(x>y){
    return 0;
  }
  ll cant=y-x+1;
  return (1+cant)*cant/2;
}
int DistanceSum(int N, int *X, int *Y){
  if(N<=2000){
    puntos.resize(N);
    for(int i=0;i<N;i++){
      puntos[i]={X[i],Y[i]};
      minix=min(minix,X[i]-1);
      miniy=min(miniy,Y[i]-1);
    }
    for(int i=0;i<N;i++){
      puntos[i].first-=minix;
      puntos[i].second-=miniy;
      existe[puntos[i].first][puntos[i].second]=true;
    }
    for(int i=0;i<N;i++){
      //bfs
      ll suma=0;
      queue<pair<int,int>> bfs;
      bfs.push(puntos[i]);
      while(!bfs.empty()){
        pair<int,int> top=bfs.front();
        bfs.pop();
        suma+=dist[top.first][top.second];
        if(dist[top.first-1][top.second]==0 && existe[top.first-1][top.second]){
          dist[top.first-1][top.second]=dist[top.first][top.second]+1;
          bfs.push({top.first-1,top.second});
        }
        if(dist[top.first+1][top.second]==0 && existe[top.first+1][top.second]){
          dist[top.first+1][top.second]=dist[top.first][top.second]+1;
          bfs.push({top.first+1,top.second});
        }
        if(dist[top.first][top.second-1]==0 && existe[top.first][top.second-1]){
          dist[top.first][top.second-1]=dist[top.first][top.second]+1;
          bfs.push({top.first,top.second-1});
        }
        if(dist[top.first][top.second+1]==0 && existe[top.first][top.second+1]){
          dist[top.first][top.second+1]=dist[top.first][top.second]+1;
          bfs.push({top.first,top.second+1});
        }
      }
      tot+=suma-2;
      bfs.push(puntos[i]);
      dist[puntos[i].first][puntos[i].second]=0;
      while(!bfs.empty()){
        pair<int,int> top=bfs.front();
        bfs.pop();
        if(dist[top.first-1][top.second]!=0){
          dist[top.first-1][top.second]=0;
          bfs.push({top.first-1,top.second});
        }
        if(dist[top.first+1][top.second]!=0){
          dist[top.first+1][top.second]=0;
          bfs.push({top.first+1,top.second});
        }
        if(dist[top.first][top.second-1]!=0){
          dist[top.first][top.second-1]=0;
          bfs.push({top.first,top.second-1});
        }
        if(dist[top.first][top.second+1]!=0){
          dist[top.first][top.second+1]=0;
          bfs.push({top.first,top.second+1});
        }
      }
    }
    return tot/2;
  }else{
    res_temp.resize(N);
    res_abs.resize(N);
    puntos.resize(N);
    psum_nivel.resize(N);
    bound_nivel.assign(N,{1e9,-1e9});
    for(int i=0;i<N;i++){
      puntos[i]={X[i],Y[i]};
      minix=min(minix,X[i]);
      miniy=min(miniy,Y[i]);
    }
    for(int i=0;i<N;i++){
      puntos[i].first-=minix;
      puntos[i].second-=miniy;
      bound_nivel[puntos[i].first].first=min(bound_nivel[puntos[i].first].first,puntos[i].second);
      bound_nivel[puntos[i].first].second=max(bound_nivel[puntos[i].first].second,puntos[i].second);
    }
    sort(ALL(puntos));
    psum_nivel[0]=bound_nivel[0].second-bound_nivel[0].first+1;
    for(int i=1;i<N;i++){
      psum_nivel[i]=psum_nivel[i-1]+bound_nivel[i].second-bound_nivel[i].first+1;
    }
    res_abs[0]=sumar(bound_nivel[0].first+1,bound_nivel[0].second);
    for(int i=1;i<N;i++){
      if(puntos[i].first==puntos[i-1].first){
        res_abs[i]=res_abs[i-1]+puntos[i].second-bound_nivel[puntos[i].first].first-(bound_nivel[puntos[i].first].second-puntos[i].second+1);
      }else if(binary_search(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))){
        res_abs[i]=res_abs[lower_bound(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))-puntos.begin()];
        res_abs[i]+=psum_nivel[puntos[i].first-1];
        res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
      }else{
        /*
        caso:
        .**.
        ****
        ***.
        */
        int pos=lower_bound(ALL(puntos),make_pair(puntos[i].first-1,0))-puntos.begin();
        res_abs[i]=res_abs[pos];
        res_abs[i]+=(abs(puntos[i].first-puntos[pos].first)+abs(puntos[i].second-puntos[pos].second))*psum_nivel[puntos[pos].first];
        res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
      }
    }
    for(int i=0;i<N;i++){
      res_temp[i]=res_abs[i];
      res_temp[i]-=sumar(bound_nivel[puntos[i].first].first,puntos[i].second-1);
      //res_temp[i]-=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
      tot+=res_temp[i];
    }
    /*for(int i=0;i<N;i++){
      tot+=sumar(bound_nivel[i].first,bound_nivel[i].second);
    }*/
    return tot;
  }
}

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