제출 #1243759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243759		simplemind_31	이상적인 도시 (IOI12_city)	C++20	32 / 100	1092 ms	2628 KiB

city

#include <bits/stdc++.h>
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;
int DistanceSum(int N, int *X, int *Y){
  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;
}

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