Submission #803189

#TimeUsernameProblemLanguageResultExecution timeMemory
803189pavementIdeal city (IOI12_city)C++17
11 / 100
1080 ms2016 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair using ii = pair<int, int>; int dist[100005], dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0}; bool vis[100005]; map<ii, int> mpp; queue<ii> Q; const int MOD = (int)1e9; int DistanceSum(int N, int X[], int Y[]) { int ans = 0; for (int i = 0; i < N; i++) { mpp[mp(X[i], Y[i])] = i; } for (int i = 0; i < N; i++) { Q.emplace(X[i], Y[i]); for (int j = 0; j < N; j++) vis[j] = 0; vis[i] = 1; dist[i] = 0; while (!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (mpp.find(mp(nx, ny)) != mpp.end()) { int idx = mpp[mp(nx, ny)]; if (!vis[idx]) { vis[idx] = 1; dist[idx] = dist[mpp[mp(x, y)]] + 1; ans = (ans + dist[idx]) % MOD; Q.emplace(X[idx], Y[idx]); } } } } } 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...