답안 #50872 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50872	2018-06-13T20:45:28 Z	Mamnoon_Siam	이상적인 도시 (IOI12_city)	C++17	100 / 100	488 ms	28240 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);
	}
};
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

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

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

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

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

답안 #50872

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