Submission #810496

#TimeUsernameProblemLanguageResultExecution timeMemory
810496AkramElOmraniIdeal city (IOI12_city)C++17
11 / 100
1075 ms1876 KiB
#include <bits/stdc++.h> using namespace std; template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); const int mod = 1e9; void add(int& a, int b) { a += b; if(a > mod) { a -= mod; } } vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int DistanceSum(int n, int *X, int *Y) { int sum = 0; map<pair<int, int>, int> mp; for(int i = 0; i < n; ++i) { mp[{X[i], Y[i]}] = i; } const int INF = 1e9 + 5; int ans = 0; for(int i = 0; i < n; ++i) { // start a bfs vector<int> dist(n, INF); queue<int> q; q.push(i); dist[i] = 0; while(!q.empty()) { int sz = q.size(); for(int i = 0; i < sz; ++i) { int p = q.front(); q.pop(); for(auto[row, col] : dir) { row += X[p]; col += Y[p]; auto it = mp.find({row, col}); if(it == mp.end()) continue; if(dist[it->second] != INF) continue; dist[it->second] = dist[p] + 1; q.push(it->second); } } } // dbg(dist) for(int j = i + 1; j < n; ++j) { add(ans, dist[j]); // dbg(ans, dist[j]) } } return ans; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:22:6: warning: unused variable 'sum' [-Wunused-variable]
   22 |  int sum = 0;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...