Submission #761103

#TimeUsernameProblemLanguageResultExecution timeMemory
761103NothingXDIdeal city (IOI12_city)C++17
32 / 100
125 ms1180 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef complex<ld> point; void debug_out(){cerr << endl;} template<typename H, typename... T> void debug_out(H h, T... t){ cerr << h << ' '; debug_out(t...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 2e3 + 10; const int inf = 2147483647; const int mod = 1e9; int add(int x, int y){ int res = x + y; if (res >= mod) return res - mod; if (res < 0) return res + mod; return res; } int n, x[maxn], y[maxn], cnt[maxn], dis[maxn], h[maxn][maxn]; bool mark[maxn][maxn]; int xc[4] = {1, -1, 0, 0}; int yc[4] = {0, 0, 1, -1}; void bfs(int sx, int sy){ for (int i = 1; i <= n; i++) h[x[i]][y[i]] = -1; h[sx][sy] = 0; queue<pii> q; q.push({sx, sy}); while(!q.empty()){ int xv = q.front().F, yv = q.front().S; q.pop(); for (int i = 0; i < 4; i++){ int xu = xv + xc[i], yu = yv + yc[i]; if (mark[xu][yu] && h[xu][yu] == -1){ h[xu][yu] = h[xv][yv] + 1; q.push({xu, yu}); } } } } int DistanceSum(int N, int *X, int *Y) { n = N; int mnx = inf, mny = inf, mx = 0; for (int i = 1; i <= n; i++){ x[i] = X[i-1]; y[i] = Y[i-1]; mnx = min(mnx, x[i]); mny = min(mny, y[i]); mx = max(mx, x[i]); } mnx--; mny--; for (int i = 1; i <= n; i++){ x[i] -= mnx; y[i] -= mny; mark[x[i]][y[i]] = true; } int ans = 0; for (int i = 1; i <= n; i++){ bfs(x[i], y[i]); for (int j = i; j <= n; j++){ ans = add(ans, h[x[j]][y[j]]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...