oj.uz

Submission #23668

# Submission time Handle Problem Language Result Execution time Memory
23668 2017-05-18T12:12:22 Z Hiasat Ideal city (IOI12_city) C++14
55 / 100
 143 ms 8552 KB 
#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

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) {
                     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2224 KB Output is correct
2 Correct 0 ms 2224 KB Output is correct
3 Correct 0 ms 2224 KB Output is correct
4 Correct 0 ms 2224 KB Output is correct
5 Correct 0 ms 2224 KB Output is correct
6 Correct 0 ms 2224 KB Output is correct
7 Correct 0 ms 2224 KB Output is correct
8 Correct 0 ms 2224 KB Output is correct
9 Correct 0 ms 2224 KB Output is correct
10 Correct 0 ms 2224 KB Output is correct
11 Correct 0 ms 2224 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2356 KB Output is correct
2 Correct 29 ms 2356 KB Output is correct
3 Correct 76 ms 2500 KB Output is correct
4 Correct 76 ms 2500 KB Output is correct
5 Correct 136 ms 2488 KB Output is correct
6 Correct 113 ms 2488 KB Output is correct
7 Correct 143 ms 2488 KB Output is correct
8 Correct 116 ms 2488 KB Output is correct
9 Correct 113 ms 2488 KB Output is correct
10 Correct 113 ms 2488 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3612 KB Output is correct
2 Correct 13 ms 3612 KB Output is correct
3 Correct 36 ms 5080 KB Output is correct
4 Correct 39 ms 5080 KB Output is correct
5 Correct 86 ms 8552 KB Output is correct
6 Correct 89 ms 8552 KB Output is correct
7 Correct 89 ms 8552 KB Output is correct
8 Correct 79 ms 8552 KB Output is correct
9 Correct 76 ms 8552 KB Output is correct
10 Correct 76 ms 8552 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3612 KB Output isn't correct
2 Halted 0 ms 0 KB -