oj.uz

Submission #121105

# Submission time Handle Problem Language Result Execution time Memory
121105 2019-06-26T06:26:08 Z MAMBA Ideal city (IOI12_city) C++17
100 / 100
 177 ms 7916 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

typedef pair<int , int> pii;
typedef long long ll;

inline int bn(vector<pii> &vec, pii p) {
	int res = lower_bound(all(vec) , p) - vec.begin();
	if (res == vec.size() || vec[res] != p) return -1;
	return res;
}

struct dsu {
	vector<int> par , sz;
	dsu() {}
	dsu(int N) {
		par.resize(N);
		iota(all(par) , 0);
		sz.resize(N , 1);
	}
	int getPar(int v) { return par[v] == v ? v : par[v] = getPar(par[v]); }
	void merge(int v, int u) {
		v = getPar(v), u = getPar(u);
		if (v == u) return;
		par[v] = u;
		sz[u] += sz[v];
	}
} ds;

ll MOD = 1e9;

vector<pii> vec, L, R;
map<int , int> mp;
map<int , set<int>> adj;
bitset<2 * 1000 * 1000 + 10> mark;
ll sz[2 * 1000 * 1000 + 10];

int dfs1(int v, int par = -1) {
	sz[v] = mp[v];
	for (auto e : adj[v])
		if (e ^ par) 
			sz[v] += dfs1(e , v);
	return sz[v] %= MOD;
}

int dfs2(int v, int par = -1, ll all = -1) {
	mark[v] = true;
	if (all == -1) all = sz[v];
	ll res = (all - sz[v]) * sz[v];
	res %= MOD;
	for (auto e : adj[v])
		if (e ^ par) 
			res += dfs2(e , v, all);
	return res % MOD;
}


int solve(int N, int *X, int *Y) {

	vec = vector<pii>(N);
	L = vector<pii>(N);
	R = vector<pii>(N);
	mark.reset();

	rep(i , 0 , N)
		vec[i] = {X[i] , Y[i]};
	sort(all(vec)); 
	{
		ds = dsu(N);
		int last = 0;
		auto relax = [&last](int now) {
			rep(j , last , now) {
				int h = bn(vec , {vec[j].first - 1 , vec[j].second});
				int v = bn(vec , {vec[j].first , vec[j].second - 1});
				if (h != -1)
					ds.merge(j , h);
				if (v != -1)
					ds.merge(j , v);
			}
			rep(j , last , now)
				L[j] = {ds.sz[ds.getPar(j)] , ds.getPar(j)};
			last = now;

		};
		rep(i , 0 , N) 
			if (vec[i].first != vec[last].first) relax(i);
		relax(N);	
	}
	{
		ds = dsu(N);
		int last = N - 1;
		auto relax = [&last](int now) {
			for (int j = last; j > now; j--) {
				int h = bn(vec , {vec[j].first + 1 , vec[j].second});
				int v = bn(vec , {vec[j].first , vec[j].second + 1});
				if (~h)
					ds.merge(j , h);
				if (~v)
					ds.merge(j , v);
			}
			for (int j = last; j > now; j--)
				R[j] = {ds.sz[ds.getPar(j)] , ds.getPar(j)};
			last = now;

		};
		for (int i = N - 1; ~i; i--)
			if (vec[i].first != vec[last].first) relax(i);
		relax(-1);	
	}
	ll res = 0;
	rep(i , 1 , N)
		if (vec[i].first != vec[i - 1].first) {
			mp.clear();
			adj.clear();
			int l = i - 1;
			while (l && vec[l - 1].first == vec[l].first) l--;
			rep	(j , l , i) {
				mp[L[j].second] = L[j].first;
				int h = bn(vec, {vec[j].first + 1 , vec[j].second});
				if (~h) {
					mp[R[h].second + N] = R[h].first;
					adj[L[j].second].insert(R[h].second + N);
					adj[R[h].second + N].insert(L[j].second);
				}
			}
			ll local = 0;
			for (auto e : mp) {
				int v = e.first;
				if (!mark[v]) {
					dfs1(v);
					local += dfs2(v);
				}
			}	
			for (auto e : mp) {
				int v = e.first;
				mark[v] = false;
			}	
			res = (res + local) % MOD;
		}
	return res % MOD;
}

int DistanceSum(int N  ,int *X , int *Y) {
	return (solve(N , X , Y) + solve(N , Y , X)) % MOD;
}

Compilation message

city.cpp: In function 'int bn(std::vector<std::pair<int, int> >&, pii)':
city.cpp:14:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (res == vec.size() || vec[res] != p) return -1;
      ~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 4 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2008 KB Output is correct
2 Correct 22 ms 1920 KB Output is correct
3 Correct 54 ms 3568 KB Output is correct
4 Correct 56 ms 3416 KB Output is correct
5 Correct 106 ms 6548 KB Output is correct
6 Correct 111 ms 6128 KB Output is correct
7 Correct 115 ms 6436 KB Output is correct
8 Correct 106 ms 6188 KB Output is correct
9 Correct 113 ms 6136 KB Output is correct
10 Correct 117 ms 6216 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2272 KB Output is correct
2 Correct 29 ms 2240 KB Output is correct
3 Correct 83 ms 4212 KB Output is correct
4 Correct 75 ms 4208 KB Output is correct
5 Correct 177 ms 7772 KB Output is correct
6 Correct 136 ms 7784 KB Output is correct
7 Correct 167 ms 7916 KB Output is correct
8 Correct 134 ms 7752 KB Output is correct
9 Correct 127 ms 7752 KB Output is correct
10 Correct 131 ms 7848 KB Output is correct