답안 #93800 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93800	2019-01-11T12:31:44 Z	pranjalssh	이상적인 도시 (IOI12_city)	C++14	100 / 100	123 ms	21748 KB

city

/*
	Consider horizontal segments as one node. A graph then when edge b/w segments if touch will be a tree.
	Do a dp to count all paths. Perform 2 dfs to count paths into subtree and upwards.

	Complexity is SUM (degree * segment size). Passes due to weak tc. Although can be optimized to linear by careful prefix sums;
	I believe if complexity is too large, considering vertical segments will be helpful(and vice versa).
*/

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

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const ll inf = 2e9;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


ii intersect(ii a, ii b) {
	return ii(max(a.F, b.F), min(a.S, b.S));
}

#define get(x,y) (lower_bound(all(a),ii(x,y))-a.begin())

int DistanceSum(int N, int *X, int *Y) {
	int n = N;
	vector<ii> a(n);
	FOR (i, 0, n - 1) {
		a[i] = ii(X[i], Y[i]);
	}
	sort(all(a));
	map<ii, int> no;
	vector<ii> sg;
	vector<vi> t(n);
	
	FOR (i, 0, n - 1) {
		int x = a[i].F, y = a[i].S;
		int j = i;
		while (j+1 < n and a[j+1].F == x and a[j+1].S == a[j].S+1) ++j;
		FOR (it, i, j) no[a[it]] = sz(sg);
		FOR (it, i, j) {
			ii cur(a[it].F-1,a[it].S);
			if (no.count(cur)) {
				t[sz(sg)].emplace_back(no[cur]);
				t[no[cur]].emplace_back(sz(sg));
			}
		}
		sg.emplace_back(i, j);
		i = j;
	}
	FOR (i, 0, n - 1) {
		sort(all(t[i])); t[i].erase(unique(all(t[i])), t[i].end());
	}
	// pr(t);
	ll ans = 0;
	vector<ll> down(n), up(n), same(n);
	vector<ll> downC(n), upC(n), sameC(n);
	function<void(int,int)> dfsD = [&](int u, int par) {

		for (int v: t[u]) if (v != par) dfsD(v, u);

		int i = sg[u].F, j = sg[u].S;
		int x = a[i].F, y1 = a[i].S, y2 = a[j].S;

		int l = 0, r = j-i;
		// pr(t);
		FOR (it, i, j) {
			int y = a[it].S;
			sameC[it] = l + r + 1;
			same[it] = (r*(r+1LL)/2 + l*(l+1LL)/2) % inf;
			++l, --r;
			for (int v: t[u]) if (v != par) {
				ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));

				int ptr = -1;
				if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
				else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
				else ptr = get(a[sg[v].F].F, pt.S);

				ll d = 1 + abs(y - a[ptr].S);
				// pr(a[it],a[ptr]);
				// pr(a[it],v,d);
				downC[it] += downC[ptr] + sameC[ptr];
				down[it] = (down[it] + d * downC[ptr] + down[ptr]) % inf;
				down[it] = (down[it] + d * sameC[ptr] + same[ptr]) % inf;
			}
			// pr(a[it], down[it]);
		}
		
	};


	function<void(int,int)> dfsU = [&](int u, int par) {

		int i = sg[u].F, j = sg[u].S;
		int x = a[i].F, y1 = a[i].S, y2 = a[j].S;

		FOR (it, i, j) if (par>=0) {
			int y = a[it].S;
			
			int v = par;
			ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));

			int ptr = -1;
			if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
			else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
			else ptr = get(a[sg[v].F].F, pt.S);

			ll d = 1 + abs(y - a[ptr].S);
			upC[it] += upC[ptr] + sameC[ptr];
			upC[it] += downC[ptr] - downC[it] - sameC[it];

			up[it] = (up[it] + d*upC[ptr] + up[ptr] + same[ptr] + d*sameC[ptr]) % inf;
			up[it] = (up[it] + d*downC[ptr] + down[ptr]) % inf;
			int o = get(x,a[ptr].S);
			// pr(a[it], par, a[ptr], a[o]);
			up[it] = (up[it] - (d+1)*downC[o] - down[o])%inf;
			up[it] = (up[it] - (d+1)*sameC[o] - same[o])%inf;
			if (up[it] < 0) up[it] += inf;
			// pr(a[it], a[ptr], upC[it]);
		}

		for (int v: t[u]) if (v != par) dfsU(v, u);
		
	};


	dfsD(0, -1);
	dfsU(0, -1);

	FOR (i, 0, n - 1) ans = (ans + up[i] + down[i] + same[i]) % inf;
	
	return ans/2;
}

// int main() {
// 	int n; cin >> n;
// 	vi x(n), y(n);
// 	FOR (i, 0, n - 1)cin >> x[i] >> y[i];
// 	cout << DistanceSum(n, &x[0], &y[0]) << "\n";
// }

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:50:19: warning: unused variable 'y' [-Wunused-variable]
   int x = a[i].F, y = a[i].S;
                   ^
city.cpp: In lambda function:
city.cpp:76:7: warning: unused variable 'x' [-Wunused-variable]
   int x = a[i].F, y1 = a[i].S, y2 = a[j].S;
       ^

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	508 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	3 ms	632 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	636 KB	Output is correct

Subtask #3
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	3704 KB	Output is correct
2	Correct	20 ms	3692 KB	Output is correct
3	Correct	48 ms	8412 KB	Output is correct
4	Correct	46 ms	8624 KB	Output is correct
5	Correct	94 ms	16632 KB	Output is correct
6	Correct	99 ms	16828 KB	Output is correct
7	Correct	98 ms	16684 KB	Output is correct
8	Correct	94 ms	16632 KB	Output is correct
9	Correct	91 ms	16760 KB	Output is correct
10	Correct	107 ms	21748 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	3832 KB	Output is correct
2	Correct	23 ms	3908 KB	Output is correct
3	Correct	55 ms	8792 KB	Output is correct
4	Correct	55 ms	8796 KB	Output is correct
5	Correct	119 ms	17236 KB	Output is correct
6	Correct	110 ms	17060 KB	Output is correct
7	Correct	123 ms	17520 KB	Output is correct
8	Correct	121 ms	17144 KB	Output is correct
9	Correct	121 ms	16632 KB	Output is correct
10	Correct	113 ms	16672 KB	Output is correct

답안 #93800

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