oj.uz

Submission #60707

# Submission time Handle Problem Language Result Execution time Memory
60707 2018-07-24T14:46:11 Z radoslav11 Ideal city (IOI12_city) C++14
100 / 100
 240 ms 42216 KB 
#include <bits/stdc++.h>
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int mod = (int)1e9;

int answer;
vector<pair<int, int> > S;

int gS(pair<int, int> x) { return lower_bound(S.begin(), S.end(), x) - S.begin() + 1; }

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

vector<int> adj[MAXN];

int par[MAXN], sz[MAXN];
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }

void unite(int u, int v)
{
	u = root(u), v = root(v);
	if(u == v) return;
	if(sz[u] > sz[v]) 
		swap(u, v);

	sz[v] += sz[u];
	par[u] = v;
}

int dp[MAXN];

void pre_dfs(int u, int pr)
{
	dp[u] = sz[root(u)];
	for(int v: adj[u])
		if(v != pr)
		{
			pre_dfs(v, u);
			dp[u] = (dp[u] + dp[v]) % mod;
		}
}

int n;

void dfs(int u, int pr)
{
	if(u != pr)
	{
		int curr = 0;
		curr = (dp[u] * 1ll * (n - dp[u])) % mod;
		answer = (answer + curr) % mod;
	}

	for(int v: adj[u])
		if(v != pr)
			dfs(v, u);
}

int DistanceSum(int N, int *X, int *Y) 
{
	::n = N;
	answer = 0;
	vector<pair<int, int> > li;
	for(int i = 0; i < N; i++)
		li.push_back({X[i], Y[i]});

	int r, idx = 0;
	for(auto it: li)
		S.push_back(it);

	sort(S.begin(), S.end());
	li = S;

	for(int i = 1; i <= n; i++) adj[i].clear();
	for(int i = 1; i <= n; i++)
		par[i] = i, sz[i] = 1;

	idx = 0;
	for(auto it: li)
	{
		idx++;
		for(int d = 0; d < 2; d++)
		{
			pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
			
			int oth = gS(nxt);
			if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
				unite(idx, oth);
		}
	}

	idx = 0;
	for(auto it: li)
	{
		idx++;
		for(int d = 2; d < 4; d++)
		{
			pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
			
			int oth = gS(nxt);
			if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
				adj[root(idx)].push_back(root(oth));
		}
	}

	for(int i = 1; i <= n; i++)
	{
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}

	r = root(1);
	pre_dfs(r, r);
	dfs(r, r);

	for(int i = 1; i <= n; i++) adj[i].clear();
	for(int i = 1; i <= n; i++)
		par[i] = i, sz[i] = 1;

	idx = 0;
	for(auto it: li)
	{
		idx++;
		for(int d = 2; d < 4; d++)
		{
			pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
			
			int oth = gS(nxt);
			if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
				unite(idx, oth);
		}
	}

	idx = 0;
	for(auto it: li)
	{
		idx++;
		for(int d = 0; d < 2; d++)
		{
			pair<int, int> nxt = {dx[d] + it.first, dy[d] + it.second};
			
			int oth = gS(nxt);
			if(oth != (int)S.size() + 1 && S[oth - 1] == nxt)
				adj[root(idx)].push_back(root(oth));
		}
	}

	for(int i = 1; i <= n; i++)
	{
		sort(adj[i].begin(), adj[i].end());
		adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
	}

	r = root(1);
	pre_dfs(r, r);
	dfs(r, r);

	return answer;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24952 KB Output is correct
2 Correct 31 ms 25064 KB Output is correct
3 Correct 24 ms 25064 KB Output is correct
4 Correct 30 ms 25064 KB Output is correct
5 Correct 29 ms 25180 KB Output is correct
6 Correct 31 ms 25180 KB Output is correct
7 Correct 27 ms 25180 KB Output is correct
8 Correct 28 ms 25180 KB Output is correct
9 Correct 30 ms 25180 KB Output is correct
10 Correct 33 ms 25248 KB Output is correct
11 Correct 30 ms 25248 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 25292 KB Output is correct
2 Correct 27 ms 25292 KB Output is correct
3 Correct 29 ms 25428 KB Output is correct
4 Correct 30 ms 25428 KB Output is correct
5 Correct 32 ms 25428 KB Output is correct
6 Correct 35 ms 25428 KB Output is correct
7 Correct 33 ms 25428 KB Output is correct
8 Correct 32 ms 25428 KB Output is correct
9 Correct 31 ms 25428 KB Output is correct
10 Correct 28 ms 25452 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26472 KB Output is correct
2 Correct 47 ms 26600 KB Output is correct
3 Correct 91 ms 28652 KB Output is correct
4 Correct 92 ms 28900 KB Output is correct
5 Correct 153 ms 32952 KB Output is correct
6 Correct 153 ms 33732 KB Output is correct
7 Correct 179 ms 34352 KB Output is correct
8 Correct 158 ms 35328 KB Output is correct
9 Correct 153 ms 35616 KB Output is correct
10 Correct 176 ms 38212 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 38212 KB Output is correct
2 Correct 63 ms 38212 KB Output is correct
3 Correct 124 ms 38212 KB Output is correct
4 Correct 123 ms 38212 KB Output is correct
5 Correct 217 ms 38396 KB Output is correct
6 Correct 197 ms 39156 KB Output is correct
7 Correct 240 ms 40220 KB Output is correct
8 Correct 170 ms 40968 KB Output is correct
9 Correct 187 ms 41420 KB Output is correct
10 Correct 196 ms 42216 KB Output is correct