oj.uz

Submission #118441

# Submission time Handle Problem Language Result Execution time Memory
118441 2019-06-19T03:40:12 Z E869120 Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 30504 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
using namespace std;

long long N, X[100009], Y[100009], col[100009], cnt[100009], rem, dp[100009]; bool used[100009];
long long ans, mod = 1000000000;
vector<int>G[100009];

void dfs1(int pos, long long dep) {
	used[pos] = true;
	rem += dep * cnt[pos]; dp[pos] = cnt[pos];
	for (int i = 0; i < G[pos].size(); i++) {
		if (used[G[pos][i]] == true) continue;
		dfs1(G[pos][i], dep + 1);
		dp[pos] += dp[G[pos][i]];
	}
}

void dfs2(int pos) {
	ans += 1LL * cnt[pos] * rem; used[pos] = true;
	for (int i = 0; i < G[pos].size(); i++) {
		if (used[G[pos][i]] == true) continue;
		rem -= (dp[G[pos][i]]) - (N - dp[G[pos][i]]);
		dfs2(G[pos][i]);
		rem += (dp[G[pos][i]]) - (N - dp[G[pos][i]]);
	}
}

long long solve() {
	rem = 0; ans = 0;
	for (int i = 0; i <= N; i++) { G[i].clear(); col[i] = 0; cnt[i] = 0; dp[i] = 0; used[i] = false; }

	vector<tuple<long long, long long, int>>vec;
	map<pair<long long, long long>, int>Map, Map2;
	for (int i = 0; i < N; i++) {
		Map[make_pair(X[i], Y[i])] = i + 1;
		vec.push_back(make_tuple(X[i], Y[i], i));
	}
	sort(vec.begin(), vec.end());

	int cnts = 0;
	for (int i = 0; i < vec.size(); i++) {
		if (col[get<2>(vec[i])] >= 1) continue;
		int ex = get<0>(vec[i]), ey = get<1>(vec[i]); cnts++;
		while (true) {
			int num = Map[make_pair(1LL * ex, 1LL * ey)] - 1;
			col[num] = cnts; cnt[cnts]++;
			ey++;
			if (Map[make_pair(ex, ey)] == 0) break;
		}
	}

	for (int i = 0; i < N; i++) {
		int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
		for (int j = 0; j < 4; j++) {
			int ex = X[i] + dx[j], ey = Y[i] + dy[j];
			if (Map[make_pair(ex, ey)] == 0) continue;
			int t1 = i, t2 = Map[make_pair(ex, ey)] - 1;
			t1 = col[t1]; t2 = col[t2];
			if (Map2[make_pair(t1, t2)] == 1 || t1 == t2) continue;
			G[t1].push_back(t2); Map2[make_pair(t1, t2)] = 1;
			G[t2].push_back(t1); Map2[make_pair(t2, t1)] = 1;
		}
	}

	dfs1(1, 0);
	for (int i = 1; i <= cnts; i++) used[i] = false;
	dfs2(1);
	return ans;
}

int DistanceSum(int NN, int *AX, int *AY) {
	N = NN; long long finalans = 0;
	for (int i = 0; i < N; i++) { X[i] = AX[i]; Y[i] = AY[i]; }
	for (int i = 0; i < 2; i++) {
		long long ret = solve();
		finalans += ret;
		for (int j = 0; j < N; j++) swap(X[j], Y[j]);
	}
	return (finalans / 2LL) % mod;
}

Compilation message

city.cpp: In function 'void dfs1(int, long long int)':
city.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
city.cpp: In function 'void dfs2(int)':
city.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
city.cpp: In function 'long long int solve()':
city.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 7 ms 2944 KB Output is correct
3 Correct 9 ms 3072 KB Output is correct
4 Correct 10 ms 3072 KB Output is correct
5 Correct 12 ms 3328 KB Output is correct
6 Correct 11 ms 3200 KB Output is correct
7 Correct 12 ms 3360 KB Output is correct
8 Correct 11 ms 3072 KB Output is correct
9 Correct 10 ms 3072 KB Output is correct
10 Correct 11 ms 3072 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6252 KB Output is correct
2 Correct 99 ms 6412 KB Output is correct
3 Correct 327 ms 10784 KB Output is correct
4 Correct 319 ms 11096 KB Output is correct
5 Correct 836 ms 18264 KB Output is correct
6 Correct 881 ms 18936 KB Output is correct
7 Correct 836 ms 17496 KB Output is correct
8 Execution timed out 1042 ms 16756 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 8412 KB Output is correct
2 Correct 121 ms 7380 KB Output is correct
3 Correct 594 ms 16760 KB Output is correct
4 Correct 539 ms 14228 KB Output is correct
5 Execution timed out 1074 ms 30504 KB Time limit exceeded
6 Halted 0 ms 0 KB -