Submission #547421

#TimeUsernameProblemLanguageResultExecution timeMemory
547421tabrIdeal city (IOI12_city)C++17
32 / 100
1090 ms3080 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif int DistanceSum(int n, int x[], int y[]) { map<pair<int, int>, int> mp; for (int i = 0; i < n; i++) { mp[make_pair(x[i], y[i])] = i; } vector<vector<int>> g(n); int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; for (int i = 0; i < n; i++) { for (int dir = 0; dir < 4; dir++) { int nx = x[i] + dx[dir]; int ny = y[i] + dy[dir]; if (mp.count(make_pair(nx, ny))) { g[i].emplace_back(mp[make_pair(nx, ny)]); } } } const int mod = (int) 1e9; int res = 0; for (int r = 0; r < n; r++) { vector<int> d(n, -1); queue<int> que; d[r] = 0; que.emplace(r); while (!que.empty()) { int v = que.front(); que.pop(); for (int to : g[v]) { if (d[to] == -1) { d[to] = d[v] + 1; que.emplace(to); } } } for (int i = r + 1; i < n; i++) { res += d[i]; res %= mod; } } return res; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); int n = 11; int x[] = {2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5}; int y[] = {5, 6, 3, 6, 3, 4, 5, 6, 3, 4, 6}; cout << DistanceSum(n, x, y) << '\n'; return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...