Submission #23668

#TimeUsernameProblemLanguageResultExecution timeMemory
23668HiasatIdeal city (IOI12_city)C++14
55 / 100
143 ms8552 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll res = 0; void sum(vector<ll> &x, vector<ll> &preX, ll X) { ll idx = lower_bound(x.begin(), x.end(), X) - x.begin(); if (idx) { res += (idx + 1) * X - preX[idx]; } if (idx != preX.size()) { res += (preX.back() - (!idx ? 0 : preX[idx - 1])) - 1ll * (preX.size() - idx) * X; } } vector<ll> preX, preY, x, y; map< pair<int, int> , int > got; int cost[2100]; vector<int> adj[2100]; int dx[4] = {0, 0, -1, 1}; int dy[4] = { -1, 1, 0, 0}; int DistanceSum(int N, int *X, int *Y) { for (int i = 0; i < N; ++i) { preX.push_back(X[i]); x.push_back(X[i]); } for (int i = 0; i < N; ++i) { preY.push_back(Y[i]); y.push_back(Y[i]); } if (N <= 2000) { for (int i = 0 ; i < N ; i++) { got[make_pair(X[i], Y[i])] = i; } for(int i = 0 ; i < N ; i++){ for(int p = 0 ; p < 4 ; p++){ int newX = X[i] + dx[p]; int newY = Y[i] + dy[p]; if(got.find(make_pair(newX,newY)) != got.end()){ adj[i].push_back(got[make_pair(newX,newY)]); } } } for (int i = 0 ; i < N ; i++) { queue< int > q; memset(cost,-1,sizeof cost); q.push(i); cost[i] = 0; while (q.size()) { int src = q.front(); q.pop(); for (int p = 0 ; p < adj[src].size(); p++) { int v = adj[src][p]; if(cost[v] == -1){ cost[v] = cost[src] + 1; q.push(v); } } } for (int j = i + 1 ; j < N ; j++) { res += cost[j]; } } return res; } sort(x.begin(), x.end()); sort(y.begin(), y.end()); sort(preX.begin(), preX.end()); sort(preY.begin(), preY.end()); for (int i = 1 ; i < preX.size(); ++i) { preX[i] += preX[i - 1]; } for (int i = 1 ; i < preY.size(); ++i) { preY[i] += preY[i - 1]; } for (int i = 0 ; i < N ; i++) { sum(x, preX, X[i]); sum(y, preY, Y[i]); } return (res / 2) % 1000000000; }

Compilation message (stderr)

city.cpp: In function 'void sum(std::vector<long long int>&, std::vector<long long int>&, ll)':
city.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (idx != preX.size()) {
          ^
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int p = 0 ; p < adj[src].size(); p++) {
                        ^
city.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < preX.size(); ++i) {
                     ^
city.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < preY.size(); ++i) {
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...