Submission #1163346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163346		HappyCapybara	Ideal city (IOI12_city)	C++20	32 / 100	1096 ms	1748 KiB

city

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

#define ll long long

int n;
ll res = 0;
vector<vector<int>> g;
vector<bool> seen;

void bfs(int s){
  seen.assign(n, false);
  queue<pair<int,ll>> q;
  q.push({s, 0});
  while (!q.empty()){
    int cur = q.front().first, d = q.front().second;
    q.pop();
    if (seen[cur]) continue;
    seen[cur] = true;
    if (cur > s) res += d;
    for (int next : g[cur]) q.push({next, d+1});
  }
}

int DistanceSum(int N, int *X, int *Y){
  n = N;
  g.resize(N);
  for (int i=0; i<N-1; i++){
    for (int j=i+1; j<N; j++){
      if (abs(X[i]-X[j])+abs(Y[i]-Y[j]) == 1){
        g[i].push_back(j);
        g[j].push_back(i);
      }
    }
  }
  for (int i=0; i<N; i++) bfs(i);
  return res % 1000000000;
}

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