oj.uz

Submission #1036223

# Submission time Handle Problem Language Result Execution time Memory
1036223 2024-07-27T06:22:58 Z abczz Ideal city (IOI12_city) C++17
100 / 100
 866 ms 211520 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37980 KB Output is correct
2 Correct 16 ms 37976 KB Output is correct
3 Correct 16 ms 37980 KB Output is correct
4 Correct 16 ms 37952 KB Output is correct
5 Correct 17 ms 37980 KB Output is correct
6 Correct 17 ms 38272 KB Output is correct
7 Correct 21 ms 38320 KB Output is correct
8 Correct 18 ms 38224 KB Output is correct
9 Correct 17 ms 38192 KB Output is correct
10 Correct 20 ms 38232 KB Output is correct
11 Correct 18 ms 38236 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39260 KB Output is correct
2 Correct 21 ms 39512 KB Output is correct
3 Correct 21 ms 40028 KB Output is correct
4 Correct 26 ms 40280 KB Output is correct
5 Correct 23 ms 40536 KB Output is correct
6 Correct 24 ms 41052 KB Output is correct
7 Correct 23 ms 40620 KB Output is correct
8 Correct 24 ms 41048 KB Output is correct
9 Correct 24 ms 41144 KB Output is correct
10 Correct 24 ms 41304 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 72396 KB Output is correct
2 Correct 151 ms 72244 KB Output is correct
3 Correct 387 ms 124472 KB Output is correct
4 Correct 395 ms 124308 KB Output is correct
5 Correct 858 ms 211396 KB Output is correct
6 Correct 804 ms 210884 KB Output is correct
7 Correct 866 ms 210116 KB Output is correct
8 Correct 843 ms 211520 KB Output is correct
9 Correct 808 ms 210116 KB Output is correct
10 Correct 648 ms 193524 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 64204 KB Output is correct
2 Correct 122 ms 68552 KB Output is correct
3 Correct 271 ms 103620 KB Output is correct
4 Correct 341 ms 114376 KB Output is correct
5 Correct 577 ms 170068 KB Output is correct
6 Correct 793 ms 198852 KB Output is correct
7 Correct 561 ms 168384 KB Output is correct
8 Correct 738 ms 198080 KB Output is correct
9 Correct 764 ms 200780 KB Output is correct
10 Correct 780 ms 202692 KB Output is correct