oj.uz

Submission #61720

# Submission time Handle Problem Language Result Execution time Memory
61720 2018-07-26T12:37:11 Z aome Ideal city (IOI12_city) C++17
23 / 100
 908 ms 61564 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int mod = 1e9;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int n, res;
int par[N];
int sz[N];
int T, low[N], num[N];
vector<int> G[N], vec[N];
vector< pair<int, int> > G2[N];
map< pair<int, int>, int > label;
map< pair<int, int>, bool > bridge;

int find(int u) {
	return u == par[u] ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
	par[find(u)] = find(v);
}

void dfs(int u, int p) {
	low[u] = num[u] = ++T;
	for (auto v : G[u]) {
		if (v == p) continue;
		if (num[v]) low[u] = min(low[u], num[v]);
		else {
			dfs(v, u), low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				bridge[{u, v}] = bridge[{v, u}] = 1;
			}
		}
	}
}

void dfs2(int u, int p) {
	sz[u] = vec[u].size();
	for (auto v : G2[u]) {
		if (p == v.first) continue;
		dfs2(v.first, u), sz[u] += sz[v.first];
	}
}

void solve(vector< pair<int, int> > vec[2]) {
	for (int i = 0; i < 2; ++i) {
		sort(vec[i].begin(), vec[i].end());
		int sum;
		sum = 0;
		for (auto j : vec[i]) {
			res = (res + 1LL * sum * j.second % mod * j.first) % mod;
			sum = (sum + j.second) % mod;
		}
		sum = 0;
		reverse(vec[i].begin(), vec[i].end());
		for (auto j : vec[i]) {
			res = (res + mod - 1LL * sum * j.second % mod * j.first % mod) % mod;
			sum = (sum + j.second) % mod;
		}
	}
}

int DistanceSum(int n, int *X, int *Y) {
	for (int i = 0; i < n; ++i) {
		label[{X[i], Y[i]}] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 4; ++j) {
			int x = X[i] + dx[j], y = Y[i] + dy[j];
			if (label.count({x, y})) {
				int id = label[{x, y}];
				G[i].push_back(id);
			}
		}
	}
	dfs(0, 0);
	for (int i = 0; i < n; ++i) par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (bridge[{i, j}]) continue;
			join(i, j);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (auto j : G[i]) {
			if (bridge[{i, j}]) {
				G2[find(i)].push_back({find(j), i});
			}
		}
	}
	for (int i = 0; i < n; ++i) vec[find(i)].push_back(i);
	for (int i = 0; i < n; ++i) {
		if (find(i) == i) {
			dfs2(i, i); break;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (find(i) != i) continue;
		for (auto j : G2[i]) {
			if (sz[i] > sz[j.first]) {
				res = (res + 1LL * sz[j.first] * (n - sz[j.first])) % mod;
			}
		}
		vector< pair<int, int> > vec2[2];
		for (auto j : vec[i]) {
			vec2[0].push_back({X[j], 1});
			vec2[1].push_back({Y[j], 1});
		}
		for (auto j : G2[i]) {
			int tmp;
			if (sz[i] > sz[j.first]) tmp = sz[j.first];
			else tmp = n - sz[i];
			vec2[0].push_back({X[j.second], tmp});
			vec2[1].push_back({Y[j.second], tmp});
		}
		solve(vec2);
	}
	return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 12 ms 7536 KB Output is correct
3 Correct 11 ms 7536 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Incorrect 10 ms 7632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 17060 KB Output is correct
2 Correct 102 ms 17256 KB Output is correct
3 Correct 340 ms 30804 KB Output is correct
4 Correct 336 ms 30872 KB Output is correct
5 Correct 799 ms 57060 KB Output is correct
6 Correct 764 ms 58500 KB Output is correct
7 Correct 809 ms 58500 KB Output is correct
8 Correct 894 ms 61420 KB Output is correct
9 Correct 908 ms 61564 KB Output is correct
10 Correct 755 ms 61564 KB Output is correct

Subtask #4
0 / 45.0

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