Submission #911319

#TimeUsernameProblemLanguageResultExecution timeMemory
911319MackerIdeal city (IOI12_city)C++17
32 / 100
112 ms1080 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define all(v) v.begin(), v.end() #define dist(x) dist[x.first][x.second] //#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") int DistanceSum(int N, int *X, int *Y) { vector<pii> v; int mxx = 0, mxy = 0; int mnx = INT_MAX, mny = INT_MAX; for (int i = 0; i < N; i++) { v.push_back({X[i], Y[i]}); mxx = max(mxx, X[i]); mxy = max(mxy, Y[i]); mnx = min(mnx, X[i]); mny = min(mny, Y[i]); } mxx -= mnx - 1; mxy -= mny - 1; for (auto &i : v) { i.first -= mnx - 1; i.second -= mny - 1; } if(N < 5000){ ll res = 0; vector<pii> off = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; vector<vector<int>> dist; dist.assign(mxx + 2, vector<int>(mxy + 2, 0)); for (auto &i : v) { for (auto &j : v) { dist(j) = INT_MAX; } queue<pii> q; q.push(i); dist(i) = 0; while(q.size()){ pii a = q.front(); q.pop(); for (auto &[dx, dy] : off) { pii b = {a.first + dx, a.second + dy}; if(dist(b) != 0 && dist(b) > dist(a) + 1){ dist(b) = dist(a) + 1; q.push(b); } } } for (auto &j : v) { res += dist(j); } } return res / 2; } }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:14:17: warning: control reaches end of non-void function [-Wreturn-type]
   14 |     vector<pii> v;
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...