# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1036223 |
2024-07-27T06:22:58 Z |
abczz |
Ideal city (IOI12_city) |
C++17 |
|
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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |