답안 #50873 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50873	2018-06-13T20:47:15 Z	Mamnoon_Siam	이상적인 도시 (IOI12_city)	C++17	100 / 100	573 ms	19968 KB

city

//#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #50873

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 21.0 / 21.0

Subtask #3 23.0 / 23.0

Subtask #4 45.0 / 45.0

Subtask #1
11.0 / 11.0

Subtask #2
21.0 / 21.0

Subtask #3
23.0 / 23.0

Subtask #4
45.0 / 45.0