Submission #742196

#TimeUsernameProblemLanguageResultExecution timeMemory
742196Hacv16Ideal city (IOI12_city)C++17
32 / 100
124 ms1108 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 2015; const int MOD = 1000000000; const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; vector<int> adj[MAX]; bool adjacent(int x1, int y1, int x2, int y2){ for(int i = 0; i < 4; i++){ int nx = x1 + dx[i], ny = y1 + dy[i]; if(nx == x2 && ny == y2) return true; } return false; } int DistanceSum(int N, int X[], int Y[]) { int resp = 0; for(int i = 0; i < N; i++) for(int j = i + 1; j < N; j++) if(adjacent(X[i], Y[i], X[j], Y[j])){ adj[i].emplace_back(j); adj[j].emplace_back(i); } for(int i = 0; i < N; i++){ queue<int> q; vector<int> dist(N, -1); q.push(i); dist[i] = 0; while(q.size()){ int u = q.front(); q.pop(); for(auto v : adj[u]){ if(dist[v] != -1) continue; dist[v] = dist[u] + 1; q.push(v); } } for(int j = 0; j < N; j++) resp += dist[j]; resp %= MOD; } return resp >> 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...