Submission #1036223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036223		abczz	Ideal city (IOI12_city)	C++17	100 / 100	866 ms	211520 KiB

city

#include <iostream>
#include <map>
#include <array>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long

using namespace std;

map <array<ll, 2>, ll> mp;
vector <array<ll, 2>> V;
vector <ll> dir;
vector <array<ll, 3> > adj[100000][16];
ll in[100000][16], M = 2e9, inv;
array <ll, 2> dp[100000][16];
queue <array<ll, 2>> Q;
array<ll, 2> operator+(array<ll, 2> A, array<ll, 2> B) {
  return {A[0]+B[0], A[1]+B[1]};
}
array<ll, 2> operator-(array<ll, 2> A, array<ll, 2> B) {
  return {A[0]-B[0], A[1]-B[1]};
}
bool B[8];
ll f = 0, nx, ny, tot = 0, dj[8][2] = {-1, -1, 0, -1, 1, -1, -1, 0, 1, 0, -1, 1, 0, 1, 1, 1};

int DistanceSum(int N, int *X, int *Y) {
  f = 0;
  for (int i=0; i<N; ++i) {
    V.push_back({X[i], Y[i]});
    mp[{X[i], Y[i]}] = i;
  }
  for (int i=0; i<N; ++i) {
    auto [x, y] = V[i];
    dir.clear();
    for (int i=0; i<8; ++i) {
      B[i] = 0;
      nx = x + dj[i][0], ny = y + dj[i][1];
      if (mp.count({nx, ny})) {
        B[i] = 1;
        dir.push_back(mp[{nx, ny}]);
      }
      else dir.push_back(-1);
    }
    for (int j=0; j<16; ++j) {
      dp[i][j] = {0, 1};
      if (B[0] && (B[1] || B[3]) && (j & 9) == 0) {
        adj[dir[0]][(ll)B[1] * 2 + (ll)B[3] * 4].push_back({i, j, 2});
      }
      if (B[1] && (j & 1) == 0) {
        adj[dir[1]][(ll)B[0]*8 + (ll)B[2] * 2 + 4].push_back({i, j, 1});
      }
      if (B[2] && (B[1] || B[4]) && (j & 3) == 0) {
        adj[dir[2]][(ll)B[1] * 8 + (ll)B[4] * 4].push_back({i, j, 2});
      }
      if (B[3] && (j & 8) == 0) {
        adj[dir[3]][(ll)B[0] * 1 + (ll)B[5] * 4 + 2].push_back({i, j, 1});
      }
      if (B[4] && (j & 2) == 0) {
        adj[dir[4]][(ll)B[2] * 1 + (ll)B[7] * 4 + 8].push_back({i, j, 1});
      }
      if (B[5] && (j & 12) == 0) {
        adj[dir[5]][(ll)B[3] * 1 + (ll)B[6] * 2].push_back({i, j, 2});
      }
      if (B[6] && (j & 4) == 0) {
        adj[dir[6]][(ll)B[5] * 8 + (ll)B[7] * 2 + 1].push_back({i, j, 1});
      }
      if (B[7] && (j & 6) == 0) {
        adj[dir[7]][(ll)B[4] * 1 + (ll)B[6] * 8].push_back({i, j, 2});
      }
    }
  }
  for (int i=0; i<N; ++i) {
    for (int j=0; j<16; ++j) {
      for (auto [x, y, t] : adj[i][j]) {
        ++in[x][y];
      }
    }
  }
  for (int i=0; i<N; ++i) {
    for (int j=0; j<16; ++j) {
      if (!in[i][j]) Q.push({i, j});
    }
  }
  while (!Q.empty()) {
    auto [x, y] = Q.front();
    Q.pop();
    for (auto [a, b, t] : adj[x][y]) {
      --in[a][b];
      dp[a][b] = dp[a][b] + (array<ll, 2>){(dp[x][y][0]+t*dp[x][y][1]) % M, dp[x][y][1]};
      if (!in[a][b]) Q.push({a, b});
    }
  }
  for (int i=0; i<N; ++i) {
    (f += dp[i][0][0]) %= M;
    //cout << X[i] << " " << Y[i] << " " << dp[i][0][0] << endl;
  }
  f /= 2;
  return f;
}

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