oj.uz

Submission #50872

# Submission time Handle Problem Language Result Execution time Memory
50872 2018-06-13T20:45:28 Z Mamnoon_Siam Ideal city (IOI12_city) C++17
100 / 100
 488 ms 28240 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

int udx[] = {-1, +0, +1, +0};
int udy[] = {+0, +1, +0, -1};

const int mod = 1e9;

struct point {
	int x, y;
	point() {x = y = 0;}
	point(int x, int y) {
		this -> x = x;
		this -> y = y;
	}
	bool operator < (const point &tmp) const {
		return x < tmp.x or (x == tmp.x and y < tmp.y);
	}
};
bool cmpx(point p, point q) {
	return (p.x < q.x) or (p.x == q.x and p.y < q.y);
}
bool cmpy(point p, point q) {
	return (p.y < q.y) or (p.y == q.y and p.x < q.x);
}

struct TreeBuilder {
	vector<point> nodes;
	vector<int> dx, dy;
	map<point, int> idx;
	vector<bool>vis;
	vector<int>comp;
	int comp_cnt;
	TreeBuilder() {}
	void build(vector<point>&vec, vector<int>Dx, vector<int>Dy, vector<ii>&edges, vector<int>&w) {
		dx = Dx, dy = Dy, nodes = vec;
		sort(all(nodes));
		vis.resize(nodes.size()); fill(all(vis), 0);
		comp.resize(nodes.size()); fill(all(comp), 0);
		idx.clear();
		for(int i = 0; i < nodes.size(); i++)
			idx[nodes[i]] = i;
		comp_cnt = 0;
		for(int i = 0; i < nodes.size(); i++) {
			if(!vis[i]) {
				dfs(i);
				comp_cnt++;
			}
		}
		for(int i = 0; i < nodes.size(); i++) {
			for(int j = 0; j < 4; j++) {
				int xx = nodes[i].x + udx[j];
				int yy = nodes[i].y + udy[j];
				if(binary_search(all(nodes), point(xx, yy))) {
					int u = i, v = idx[point(xx, yy)];
					u = comp[u], v = comp[v];
					if(u != v) {
						if(u > v) swap(u, v);
						edges.push_back(ii(u, v));
					}
				}
			}
		}
		sort(all(edges));
		KeepUnique(edges);
		w.resize(comp_cnt); fill(all(w), 0);
		for(int i = 0; i < nodes.size(); i++) {
			w[comp[i]]++;
		}
	}
	void dfs(int u) {
		vis[u] = 1;
		comp[u] = comp_cnt;
		for(int i = 0; i < 2; i++) {
			int xx = nodes[u].x + dx[i];
			int yy = nodes[u].y + dy[i];
			if(binary_search(all(nodes), point(xx, yy))) {
				int v = idx[point(xx, yy)];
				if(!vis[v]) {
					dfs(v);
				}
			}
		}
	}
}TB;

ll f(ll x) { // f(x) = \sum_{i = 1}^{x} i * (x - i + 1) = x * (x + 1) * (x + 2) / 6
	ll F = x, A = x + 1, P = x + 2;
	if(F % 2 == 0) F /= 2;
	else if(A % 2 == 0) A /= 2;
	else if(P % 2 == 0) P /= 2;
	if(F % 3 == 0) F /= 3;
	else if(A % 3 == 0) A /= 3;
	else if(P % 3 == 0) P /= 3;
	ll ret = (F * A) % mod;
	ret = (ret * P) % mod;
	return ret;
}

int n;
vector<point> pts;
vector<ii> edges;
vector<int> w, g[200010];
ll ans = 0;

int dfs(int u, int p) {
	int sz = w[u];
	for(int v : g[u]) {
		if(p - v) {
			sz += dfs(v, u);
		}
	}
	ans = (ans + ((1LL * sz * (n - sz)) % mod)) % mod;
	return sz;
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	pts.resize(n);
	for(int i = 0; i < n; i++) {
		pts[i].x = X[i], pts[i].y = Y[i];
	}
	
	edges.clear();
	w.clear();
	for(int i = 0; i < n; i++)
		g[i].clear();

	TB.build(pts, {-1, +1}, {0, 0}, edges, w);
	for(ii &b : edges) {
		int x = b.first, y = b.second;
		g[x].push_back(y);
		g[y].push_back(x);
		//cout << w[b.first] << ' ' << w[b.second] << endl;
	}

	//for(int x : w) ans = (ans + f(x-1)) % mod;
	dfs(0, -1);
	
	//cout << "----------------------" << endl;

	edges.clear();
	w.clear();
	for(int i = 0; i < n; i++)
		g[i].clear();

	TB.build(pts, {0, 0}, {-1, +1}, edges, w);
	for(ii &b : edges) {
		int x = b.first, y = b.second;
		g[x].push_back(y);
		g[y].push_back(x);
		//cout << w[b.first] << ' ' << w[b.second] << endl;
	}

	//for(int x : w) ans = (ans + f(x-1)) % mod;
	dfs(0, -1);

	return (int)ans;
}

Compilation message

city.cpp: In function 'int myrand(int, int)':
city.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
city.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
city.cpp: In member function 'void TreeBuilder::build(std::vector<point>&, std::vector<int>, std::vector<int>, std::vector<std::pair<int, int> >&, std::vector<int>&)':
city.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++)
                  ~~^~~~~~~~~~~~~~
city.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++) {
                  ~~^~~~~~~~~~~~~~
city.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++) {
                  ~~^~~~~~~~~~~~~~
city.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++) {
                  ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5616 KB Output is correct
2 Correct 8 ms 5616 KB Output is correct
3 Correct 11 ms 5768 KB Output is correct
4 Correct 9 ms 5796 KB Output is correct
5 Correct 11 ms 5824 KB Output is correct
6 Correct 13 ms 5852 KB Output is correct
7 Correct 14 ms 5884 KB Output is correct
8 Correct 11 ms 5900 KB Output is correct
9 Correct 12 ms 5912 KB Output is correct
10 Correct 12 ms 5952 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 8368 KB Output is correct
2 Correct 80 ms 8644 KB Output is correct
3 Correct 237 ms 12228 KB Output is correct
4 Correct 218 ms 12632 KB Output is correct
5 Correct 467 ms 18840 KB Output is correct
6 Correct 463 ms 19740 KB Output is correct
7 Correct 455 ms 20364 KB Output is correct
8 Correct 488 ms 21064 KB Output is correct
9 Correct 457 ms 22216 KB Output is correct
10 Correct 409 ms 26028 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 26028 KB Output is correct
2 Correct 75 ms 26028 KB Output is correct
3 Correct 192 ms 26028 KB Output is correct
4 Correct 202 ms 26028 KB Output is correct
5 Correct 378 ms 26028 KB Output is correct
6 Correct 443 ms 26028 KB Output is correct
7 Correct 380 ms 26484 KB Output is correct
8 Correct 426 ms 26680 KB Output is correct
9 Correct 436 ms 27584 KB Output is correct
10 Correct 440 ms 28240 KB Output is correct