oj.uz

Submission #50873

# Submission time Handle Problem Language Result Execution time Memory
50873 2018-06-13T20:47:15 Z Mamnoon_Siam Ideal city (IOI12_city) C++17
100 / 100
 573 ms 19968 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);
	}
};

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;

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];
	}

	// vertical
	
	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);
	}

	dfs(0, -1);
	
	// horizontal

	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);
	}

	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:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < nodes.size(); i++)
                  ~~^~~~~~~~~~~~~~
city.cpp:62: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:85: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 7 ms 4984 KB Output is correct
2 Correct 8 ms 5092 KB Output is correct
3 Correct 6 ms 5136 KB Output is correct
4 Correct 7 ms 5204 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 10 ms 5204 KB Output is correct
7 Correct 9 ms 5204 KB Output is correct
8 Correct 10 ms 5204 KB Output is correct
9 Correct 8 ms 5204 KB Output is correct
10 Correct 7 ms 5204 KB Output is correct
11 Correct 8 ms 5204 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5424 KB Output is correct
2 Correct 10 ms 5428 KB Output is correct
3 Correct 12 ms 5476 KB Output is correct
4 Correct 11 ms 5476 KB Output is correct
5 Correct 12 ms 5476 KB Output is correct
6 Correct 15 ms 5476 KB Output is correct
7 Correct 12 ms 5476 KB Output is correct
8 Correct 14 ms 5476 KB Output is correct
9 Correct 15 ms 5484 KB Output is correct
10 Correct 13 ms 5484 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7792 KB Output is correct
2 Correct 87 ms 7792 KB Output is correct
3 Correct 253 ms 11056 KB Output is correct
4 Correct 244 ms 11108 KB Output is correct
5 Correct 565 ms 16608 KB Output is correct
6 Correct 501 ms 16608 KB Output is correct
7 Correct 513 ms 16736 KB Output is correct
8 Correct 573 ms 16764 KB Output is correct
9 Correct 555 ms 16880 KB Output is correct
10 Correct 437 ms 19968 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19968 KB Output is correct
2 Correct 105 ms 19968 KB Output is correct
3 Correct 197 ms 19968 KB Output is correct
4 Correct 209 ms 19968 KB Output is correct
5 Correct 450 ms 19968 KB Output is correct
6 Correct 473 ms 19968 KB Output is correct
7 Correct 484 ms 19968 KB Output is correct
8 Correct 489 ms 19968 KB Output is correct
9 Correct 482 ms 19968 KB Output is correct
10 Correct 467 ms 19968 KB Output is correct