Submission #1237769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237769		caacrugon	이상적인 도시 (IOI12_city)	C++20	32 / 100	1095 ms	2884 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair

int DistanceSum(int N,int*X,int*Y){
  map<pair<int,int>,int> nodes;
  for(int i=0;i<N;i++){
    nodes[mkp(X[i],Y[i])]=i;
  }
  vector<vector<int>> ln(N);
  for(auto&e:nodes){
      int x=e.first.first,y=e.first.second,i=e.second;
      if(nodes.count(mkp(x+1,y)))ln[i].push_back(nodes[mkp(x+1,y)]);
      if(nodes.count(mkp(x-1,y)))ln[i].push_back(nodes[mkp(x-1,y)]);
      if(nodes.count(mkp(x,y+1)))ln[i].push_back(nodes[mkp(x,y+1)]);
      if(nodes.count(mkp(x,y-1)))ln[i].push_back(nodes[mkp(x,y-1)]);
  }
  int ans=0;
  for(int i=0;i<N;i++){
      queue<int> q;
      q.push(i);
      vector<int> dist(N,-1);
      dist[i]=0;
      while(q.size()){
          int nodo=q.front();q.pop();
          for(int v:ln[nodo]){
            if(dist[v]<0){
                dist[v]=dist[nodo]+1;
                q.push(v);
            }
          }
      }
      for(int j=i+1;j<N;j++){
        if(dist[j]>=0){
          ans=(ans+dist[j])%1000000000;
        }
      }
  }
  return ans;
}

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