oj.uz

Submission #96725

# Submission time Handle Problem Language Result Execution time Memory
96725 2019-02-11T15:02:49 Z polyfish Transport (COCI19_transport) C++14
130 / 130
 706 ms 22240 KB 
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int64_t, null_type, less_equal<int64_t>, rb_tree_tag, tree_order_statistics_node_update>;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int64_t MAX_N = 100002;
const int64_t INF = 1e18;

struct edge {
	int64_t v, w;

	edge() {}

	edge(int64_t v, int64_t w): v(v), w(w) {}
};

int64_t n, gas[MAX_N], nChildren[MAX_N];
int64_t l[MAX_N], up[MAX_N], down[MAX_N];
vector<edge> g[MAX_N];
bool deleted[MAX_N];
int64_t res;
ordered_set s1, s2;

void readInput() {

	cin >> n;

	for (int64_t i=1; i<=n; ++i)
		cin >> gas[i];

	for (int64_t i=1; i<n; ++i) {
		int64_t u, v, w;
		cin >> u >> v >> w;

		g[u].push_back(edge(v, w));
		g[v].push_back(edge(u, w));
	}
}

int64_t fixRoot(int64_t u, int64_t par) {

	nChildren[u] = 1;

	for (auto e : g[u]) {
		if (!deleted[e.v] && e.v!=par)
			nChildren[u] += fixRoot(e.v, u);
	}

	return nChildren[u];
}

int64_t findCentroid(int64_t u, int64_t par, int64_t curRoot) {

	for (auto e : g[u]) {
		if (!deleted[e.v] && e.v!=par && nChildren[e.v]>nChildren[curRoot]/2)
			return findCentroid(e.v, u, curRoot);
	}

	return u;
}

void dp(int64_t u, int64_t par) {

	up[u] = max(up[par], l[u]);
	down[u] = min(down[par], l[u] - gas[u]);

	if (l[u]-up[u]>=0)
		++res;

	if (down[u]>=0)
		++res;

	for (auto e : g[u]) {
		if (!deleted[e.v] && e.v!=par) {
			l[e.v] = l[u] - e.w + gas[e.v];
			dp(e.v, u);
		}
	}
}

void calc(int64_t u, int64_t par, int64_t root) {

	// if (root==4 && u==7)
	// 	debug(s1.order_of_key(down[u]-gas[root]+1));
	res += s1.order_of_key(down[u]-gas[root]+1);

	if (l[u]-up[u]>=0) {
		// if (root==4 && u==7)
		// 	debug(s2.order_of_key(l[u]+1));
		res += s2.order_of_key(l[u]+1);
	}

	for (auto e : g[u]) {
		if (!deleted[e.v] && e.v!=par)
			calc(e.v, u, root);
	}

}

void upd(int64_t u, int64_t par, int64_t root) {
	
	// if (u==1 && root==4)
	// 	debug(-(down[u]-gas[root]));
	s2.insert(-(down[u]-gas[root]));

	if (l[u]-up[u]>=0)
		s1.insert(-l[u]);

	for (auto e : g[u]) {
		if (!deleted[e.v] && e.v!=par)
			upd(e.v, u, root);
	}
}

void solve(int64_t u) {

	fixRoot(u, 0);
	u = findCentroid(u, 0, u);
	// debug(u);
	fixRoot(u, 0);
	deleted[u] = true;

	l[u] = gas[u];
	up[u] = l[u];
	down[u] = INF;

	for (auto e : g[u]) {
		if (!deleted[e.v]) {
			l[e.v] = gas[u] - e.w + gas[e.v];
			up[e.v] = max(up[u], l[e.v]);
			down[e.v] = min(down[u], l[e.v]-gas[e.v]);
			dp(e.v, u);
		}
	}
	// if (u==1)
	// 	debug(res);

	s1.clear();
	s2.clear();

	for (auto e : g[u]) {
		if (!deleted[e.v]) {
			calc(e.v, u, u);
			upd(e.v, u, u);
		}
	}
	// if (u==1)
	// 	debug(res);

	for (auto e : g[u]) {
		if (!deleted[e.v])
			solve(e.v);
	}
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
	ordered_set s;
	solve(1);
	cout << res;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3192 KB Output is correct
2 Correct 16 ms 3448 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3576 KB Output is correct
2 Correct 17 ms 3704 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12372 KB Output is correct
2 Correct 196 ms 10488 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 15088 KB Output is correct
2 Correct 265 ms 15944 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 19948 KB Output is correct
2 Correct 420 ms 22240 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 7800 KB Output is correct
2 Correct 83 ms 6692 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 11076 KB Output is correct
2 Correct 209 ms 9276 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 13240 KB Output is correct
2 Correct 283 ms 12792 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 15996 KB Output is correct
2 Correct 437 ms 15828 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 19688 KB Output is correct
2 Correct 621 ms 17272 KB Output is correct