oj.uz

답안 #362962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362962 2021-02-05T01:15:57 Z 8e7 이상적인 도시 (IOI12_city) C++14
55 / 100
 130 ms 5224 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <queue>
#define ll long long
#define maxn 100005
#define mod 1000000000
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<int> adj[maxn];
vector<pii> a;

int dis[maxn];
ll pref[maxn];
bool found[maxn];

int DistanceSum(int N, int *X, int *Y) {
	ll ans = 0;
	for (int i = 0;i < N;i++) {
		a.push_back(make_pair(X[i], Y[i]));
	}
	sort(a.begin(), a.end());
	if (N <= 2000) {
		for (int i = 0;i < N;i++) {
			for (int k = 0;k < 4;k++) {
				pii ne = make_pair(a[i].ff + dir[k][0], a[i].ss + dir[k][1]);
				int id = lower_bound(a.begin(), a.end(), ne) - a.begin();
				if (id < N && a[id] == ne) {
					adj[i].push_back(id);
					adj[id].push_back(i);
				}
			}
		}

		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) found[j] = 0, dis[j] = 0;
			queue<int> que;
			que.push(i);
			found[i] = 1;
			while (que.size()) {
				int cur = que.front();
				que.pop();
				ans += dis[cur];
				for (int v:adj[cur]) {
					if (!found[v]) {
						dis[v] = dis[cur] + 1;
						que.push(v);
						found[v] = 1;
					}
				}
			}
		}
		return int((ans / 2) % mod);
	} else {
		sort(X, X + N);
		sort(Y, Y + N);
		for (int i = 0;i < N;i++) {
			pref[i] = X[i] + (i ? pref[i - 1] : 0);
			ans += (ll)X[i] * i - (i ? pref[i - 1] : 0);
		}
		for (int i = 0;i < N;i++) {
			pref[i] = Y[i] + (i ? pref[i - 1] : 0);
			ans += (ll)Y[i] * i - (i ? pref[i - 1] : 0);
		}
		return ans % mod;
	}
}
/*
int main() {
	io
	int n;
	cin >> n;
	int x[n], y[n];
	for (int i = 0;i < n;i++) cin >> x[i];
	for (int i = 0;i <n ;i++) cin >> y[i];
	cout << DistanceSum(n, x, y);
}
/*
11
2 2 3 3 4 4 4 4 5 5 5
5 6 3 6 3 4 5 6 3 4 6

6
0 0 1 1 1 1
0 1 1 2 3 4
 */

Compilation message

city.cpp:86:1: warning: "/*" within comment [-Wcomment]
   86 | /*
      |

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 2924 KB Output is correct
2 Correct 33 ms 2796 KB Output is correct
3 Correct 73 ms 2836 KB Output is correct
4 Correct 72 ms 2796 KB Output is correct
5 Correct 130 ms 2816 KB Output is correct
6 Correct 116 ms 2880 KB Output is correct
7 Correct 127 ms 2796 KB Output is correct
8 Correct 118 ms 2796 KB Output is correct
9 Correct 123 ms 2796 KB Output is correct
10 Correct 122 ms 2924 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 3308 KB Output is correct
2 Correct 10 ms 3308 KB Output is correct
3 Correct 23 ms 4076 KB Output is correct
4 Correct 22 ms 4076 KB Output is correct
5 Correct 46 ms 5224 KB Output is correct
6 Correct 44 ms 5224 KB Output is correct
7 Correct 45 ms 5224 KB Output is correct
8 Correct 44 ms 5224 KB Output is correct
9 Correct 43 ms 5224 KB Output is correct
10 Correct 43 ms 5224 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 3432 KB Output isn't correct
2 Halted 0 ms 0 KB -