oj.uz

Submission #362992

# Submission time Handle Problem Language Result Execution time Memory
362992 2021-02-05T02:04:37 Z Seanliu Ideal city (IOI12_city) C++14
32 / 100
 184 ms 1004 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
 
const int MOD = 1e9, maxN = 1e5 + 326;
const long long int INF = (1LL << 31) - 2;
 
int mp[2020][2020], vis[maxN], d[maxN], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<int> que;
vector<pii> pos;
 
inline int add(int a, int b){
	return (a + b >= MOD ? a + b - MOD : a + b);
}

struct BIT{
	int arr[maxN];
	BIT(){}
	void modify(int p, int x){
		for(; p < maxN; p += (p & -p)) arr[p] = add(arr[p], x);
	}
	int sum(int p){
		int r = 0;
		for(; p; p -= (p & -p)) r = add(r, arr[p]);
		return r;
	}
} cnt, xy;
 
int DistanceSum(int N, int *X, int *Y) {
	if(N <= 2000){
		int minX = INF, minY = INF;
		for(int i = 0; i < N; i++){
			minX = min(minX, X[i]);
			minY = min(minY, Y[i]);
		}
		for(int i = 0; i < N; i++){
			X[i] -= minX - 1;
			Y[i] -= minY - 1;
			mp[X[i]][Y[i]] = i + 1;
		}
		long long int ans = 0;
		for(int i = 0; i < N; i++){
			fill(d, d + N, INF);	
			fill(vis, vis + N, false);
			d[i] = 0;
			que.push(i);
			vis[i] = true;
			//cout << "i = " << i << endl;
			while(que.size()){
				int id = que.front(); que.pop();
				for(int j = 0; j < 4; j++){
					if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
						int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
						if(!vis[nid]){
							d[nid] = d[id] + 1;
							//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
							ans = add(ans, d[nid]);
							vis[nid] = true;
							que.push(nid);
						}
					}
				}
			}
		}
		return ans / 2;
	}
	int minX = INF, minY = INF;
	for(int i = 0; i < N; i++){
		minX = min(minX, X[i]);
		minY = min(minY, Y[i]);
	}
	for(int i = 0; i < N; i++){
		X[i] -= minX - 1;
		Y[i] -= minY - 1;
		pos.emplace_back(X[i], Y[i]);
	}
	sort(pos.begin(), pos.end());	
	long long int ans = 0;
	for(auto f : pos){
		int x = f.F, y = f.S;
		ans = add(ans, MOD - xy.sum(y));
		ans = add(ans, cnt.sum(y) * add(x, y) % MOD);
		cnt.modify(y, 1);
		xy.modify(y, add(x, y));
	}
	return add(0, ans);
}

/*
int DistanceSum(int N, int *X, int *Y) {
		if(N > maxN) return 0;
		int minX = INF, minY = INF;
		for(int i = 0; i < N; i++){
			minX = min(minX, X[i]);
			minY = min(minY, Y[i]);
		}
		for(int i = 0; i < N; i++){
			X[i] -= minX - 1;
			Y[i] -= minY - 1;
			mp[X[i]][Y[i]] = i + 1;
		}
		long long int ans = 0;
		for(int i = 0; i < N; i++){
			fill(d, d + N, INF);	
			fill(vis, vis + N, false);
			d[i] = 0;
			que.push(i);
			vis[i] = true;
			//cout << "i = " << i << endl;
			while(que.size()){
				int id = que.front(); que.pop();
				for(int j = 0; j < 4; j++){
					if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
						int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
						if(!vis[nid]){
							d[nid] = d[id] + 1;
							//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
							ans = add(ans, d[nid]);
							vis[nid] = true;
							que.push(nid);
						}
					}
				}
			}
		}
		return ans / 2;
	return 5;
	int minX = INF, minY = INF;
	for(int i = 0; i < N; i++){
		minX = min(minX, X[i]);
		minY = min(minY, Y[i]);
	}
	for(int i = 0; i < N; i++){
		X[i] -= minX - 1;
		Y[i] -= minY - 1;
		pos.emplace_back(X[i], Y[i]);
	}
	sort(pos.begin(), pos.end());	
	long long int ans = 0;
	for(auto f : pos){
		int x = f.F, y = f.S;
		ans = add(ans, MOD - xy.sum(y));
		ans = add(ans, cnt.sum(y) * add(x, y) % MOD);
		cnt.modify(y, 1);
		xy.modify(y, add(x, y));
	}
	return add(0, ans);
}
*/

/*
int DistanceSum(int N, int *X, int *Y) {
	if(N > maxN) return 0;
	int minX = INF, minY = INF;
	for(int i = 0; i < N; i++){
		minX = min(minX, X[i]);
		minY = min(minY, Y[i]);
	}
	for(int i = 0; i < N; i++){
		X[i] -= minX - 1;
		Y[i] -= minY - 1;
		mp[X[i]][Y[i]] = i + 1;
	}
	long long int ans = 0;
	for(int i = 0; i < N; i++){
		fill(d, d + N, INF);	
		fill(vis, vis + N, false);
		d[i] = 0;
		que.push(i);
		vis[i] = true;
		//cout << "i = " << i << endl;
		while(que.size()){
			int id = que.front(); que.pop();
			for(int j = 0; j < 4; j++){
				if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
					int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
					if(!vis[nid]){
						d[nid] = d[id] + 1;
						//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
						ans = add(ans, d[nid]);
						vis[nid] = true;
						que.push(nid);
					}
				}
			}
		}
	}
	return ans / 2;
}
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 620 KB Output is correct
2 Correct 35 ms 492 KB Output is correct
3 Correct 95 ms 620 KB Output is correct
4 Correct 83 ms 748 KB Output is correct
5 Correct 173 ms 876 KB Output is correct
6 Correct 127 ms 876 KB Output is correct
7 Correct 184 ms 876 KB Output is correct
8 Correct 130 ms 1004 KB Output is correct
9 Correct 124 ms 620 KB Output is correct
10 Correct 121 ms 620 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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