Submission #1243762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243762		adriines06	Ideal city (IOI12_city)	C++20	32 / 100	1095 ms	2884 KiB

city

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

int DistanceSum(int N, int *X, int *Y) {
  map<pair<int,int>,int>mp;
  vector<vector<int>>adj(N);
  for(int i=0;i<N;i++){
    mp[{X[i],Y[i]}]=i;
  }
  for(auto p: mp){
    int x=p.first.first, y=p.first.second;
    int u=p.second;
    if(mp.count({x+1,y})) adj[u].push_back(mp[{x+1,y}]);
    if(mp.count({x-1,y})) adj[u].push_back(mp[{x-1,y}]);
    if(mp.count({x,y+1})) adj[u].push_back(mp[{x,y+1}]);
    if(mp.count({x,y-1})) adj[u].push_back(mp[{x,y-1}]);
  }
  int ans=0;
  for(int i=0;i<N;i++){
    vector<int>dis(N,-1);
    queue<int>q;
    q.push(i);
    dis[i]=0;
    while(!q.empty()){
      int u=q.front();
      q.pop();
      for(int v: adj[u]){
        if(dis[v]==-1){
          dis[v]=dis[u]+1;
          q.push(v);
        }
      }
    }
    for(int j=i+1;j<N;j++){
      ans+=dis[j];
    }
  }

  return ans;
}

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