Submission #124314

#TimeUsernameProblemLanguageResultExecution timeMemory
124314turbatIdeal city (IOI12_city)C++14
0 / 100
32 ms12408 KiB
#include <bits/stdc++.h> using namespace std; map <int, bool> m[100005], used[100005]; long long ans, mod = 1e9; int n; int dfs(int x, int y){ int s = 0, ty = y - 1; vector <pair <int, int> > v; while (m[x].count(ty + 1)){ s++; used[x][++ty] = 1; if (m[x + 1].count(ty)) v.push_back({x + 1, ty}); if (m[x - 1].count(ty)) v.push_back({x - 1, ty}); } ty = y; while (m[x].count(ty - 1)){ s++; used[x][--ty] = 1; if (m[x + 1].count(ty)) v.push_back({x + 1, ty}); if (m[x - 1].count(ty)) v.push_back({x - 1, ty}); } for (auto to : v) if (!used[to.first].count(to.second)) s += dfs(to.first, to.second); ans = (ans + 1ll * s * (n - s)) % mod; return s; } int dfs1(int x, int y){ int s = 0, tx = x - 1; vector <pair <int, int> > v; while (m[tx + 1].count(y)){ s++; used[++tx][y] = 1; if (m[tx].count(y + 1)) v.push_back({tx, y + 1}); if (m[tx].count(y - 1)) v.push_back({tx, y - 1}); } tx = x; while (m[tx - 1].count(y)){ s++; used[--tx][y] = 1; if (m[tx].count(y + 1)) v.push_back({tx, y + 1}); if (m[tx].count(y - 1)) v.push_back({tx, y - 1}); } for (auto to : v) if (!used[to.first].count(to.second)) s += dfs1(to.first, to.second); ans = (ans + 1ll * s * (n - s)) % mod; return s; } int DistanceSum(int N, int *X, int *Y) { n = N; int mnx = INT_MAX, mny = INT_MAX; for (int i = 0;i < n;i++){ mnx = min(mnx, X[i]); mny = min(mny, Y[i]); } int s, s1; for (int i = 0;i < n;i++){ X[i] = X[i] - mnx + 1; Y[i] = Y[i] - mny + 1; if (X[i] == 1) s = i; if (Y[i] == 1) s1 = i; m[X[i]][Y[i]] = 1; } dfs(X[s], Y[s]); for (int i = 0;i < 100005;i++) used[i].clear(); dfs1(Y[s1], X[s1]); return ans; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:71:18: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs1(Y[s1], X[s1]);
                  ^
city.cpp:69:15: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(X[s], Y[s]);
               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...