oj.uz

Submission #1036222

# Submission time Handle Problem Language Result Execution time Memory
1036222 2024-07-27T06:20:31 Z abczz Ideal city (IOI12_city) C++17
32 / 100
 147 ms 72392 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 = 1e9;
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 17 ms 37976 KB Output is correct
3 Correct 16 ms 37976 KB Output is correct
4 Correct 17 ms 37980 KB Output is correct
5 Correct 17 ms 37980 KB Output is correct
6 Correct 18 ms 38236 KB Output is correct
7 Correct 18 ms 38236 KB Output is correct
8 Correct 19 ms 38236 KB Output is correct
9 Correct 17 ms 38236 KB Output is correct
10 Correct 17 ms 38236 KB Output is correct
11 Correct 17 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 22 ms 39556 KB Output is correct
3 Correct 22 ms 39772 KB Output is correct
4 Correct 24 ms 40276 KB Output is correct
5 Correct 23 ms 40540 KB Output is correct
6 Correct 24 ms 41244 KB Output is correct
7 Correct 23 ms 40532 KB Output is correct
8 Correct 24 ms 41052 KB Output is correct
9 Correct 23 ms 41052 KB Output is correct
10 Correct 24 ms 41244 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 72392 KB Output is correct
2 Incorrect 135 ms 72388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 63948 KB Output isn't correct
2 Halted 0 ms 0 KB -