Submission #958983

#TimeUsernameProblemLanguageResultExecution timeMemory
958983vjudge1Ideal city (IOI12_city)C++17
0 / 100
146 ms5116 KiB
//#include "city.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) x.begin(), x.end() const int N = 1e4+4, inf = INT_MAX; const vector<pair<int, int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; ll ans; bitset<N> cell[N], vis[N]; bool ok(int x, int y) { return min(x, y) >= 0; } void bfs(int X, int Y) { queue<tuple<int, int, int>> q; q.push(make_tuple(0, X, Y)); while (!q.empty()) { int d = get<0>(q.front()); int x = get<1>(q.front()); int y = get<2>(q.front()); q.pop(); if (vis[x][y]) continue; vis[x][y] = 1; ans += d; for (auto [a, b] : dir) { if (ok(x+a, y+b) && cell[x+a][y+b] && !vis[x+a][y+b]) { q.push(make_tuple(d+1, x+a, y+b)); } } } } int DistanceSum(int N, int *X, int *Y) { ans = 0; /* vector<int> comp(N*2); for (int i = 0; i < N; i++) { comp[i*2] = X[i]; comp[i*2 + 1] = Y[i]; } sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); for (int i = 0; i < N; i++) { X[i] = lower_bound(all(comp), X[i]) - comp.begin(); Y[i] = lower_bound(all(comp), Y[i]) - comp.begin(); cell[X[i]][Y[i]] = 1; } */ int mn = inf; for (int i = 0; i < N; i++) { mn = min({mn, X[i], Y[i]}); } for (int i = 0; i < N; i++) { X[i] -= mn; Y[i] -= mn; cell[X[i]][Y[i]] = 1; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { vis[X[i]][Y[i]] = 0; } bfs(X[i], Y[i]); } return ans/2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...