Submission #1237685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237685		guanex	Ideal city (IOI12_city)	C++20	32 / 100	1096 ms	2884 KiB

city

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int mod = 1e9;

int bfs(int no, vector<vector<int>> &ed){
  queue<int> q;
  int vis[(int)ed.size()];
  memset(vis, -1, sizeof vis);
  q.push(no);
  vis[no] = 0;
  while((int)q.size() > 0){
    int node = q.front();
    q.pop();
    for(auto e:ed[node]){
      if(vis[e] == -1){
        vis[e] = vis[node]+1;
        q.push(e);
      }
    }
  }
  ll ans = 0;
  for(int i = 0; i < no; ++i){
    ans += vis[i];
    ans %= mod;
  }
  return ans % mod;
}

int DistanceSum(int N, int *X, int *Y) {
  map<pair<int, int>, int> nodes;
  for(int i = 0; i < N; ++i){
    nodes[{X[i], Y[i]}] = i;
  }
  vector<vector<int>> ed(N);
  for(auto e:nodes){
    int x = e.first.first;
    int y = e.first.second;
    if(nodes.count({x+1, y})){
      ed[e.second].push_back(nodes[{x+1, y}]);
    }
    if(nodes.count({x-1, y})){
      ed[e.second].push_back(nodes[{x-1, y}]);
    }
    if(nodes.count({x, y+1})){
      ed[e.second].push_back(nodes[{x, y+1}]);
    }
    if(nodes.count({x, y-1})){
      ed[e.second].push_back(nodes[{x, y-1}]);
    }
  }
  ll ans = 0;
  for(int i = 1; i < N; ++i){
    ans += bfs(i, ed);
    ans %= mod;
  }
  return ans;
}

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