Submission #1013562

#TimeUsernameProblemLanguageResultExecution timeMemory
1013562spacewalkerIdeal city (IOI12_city)C++17
0 / 100
382 ms262144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll MOD = 1'000'000'000; vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int DistanceSum(int N, int *X, int *Y) { map<pair<int, int>, int> cell_index; for (int i = 0; i < N; ++i) cell_index[{X[i], Y[i]}] = i; vector<vector<int>> graph(N); for (int i = 0; i < N; ++i) { for (auto [dx, dy] : dirs) { int nx = X[i] + dx, ny = Y[i] + dy; auto possible_index = cell_index.find({nx, ny}); if (possible_index != cell_index.end()) { graph[i].push_back(possible_index->second); } } } ll ans = 0; for (int i = 0; i < N; ++i) { vector<bool> dist(N, -1); dist[i] = 0; queue<int> q; q.push(i); while (!q.empty()) { int cur = q.front(); q.pop(); for (int nxt : graph[cur]) { dist[nxt] = dist[cur] + 1; q.push(nxt); } } ans += accumulate(dist.begin(), dist.end(), 0LL); } return ans % MOD; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...