oj.uz

Submission #96723

# Submission time Handle Problem Language Result Execution time Memory
96723 2019-02-11T14:54:12 Z polyfish Transport (COCI19_transport) C++14
78 / 130
 700 ms 16416 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<int, null_type, less_equal<int>, 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 (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

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

struct edge {
	int v, w;

	edge() {}

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

int 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 (int i=1; i<=n; ++i)
		cin >> gas[i];

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

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

int fixRoot(int u, int 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];
}

int findCentroid(int u, int par, int 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(int u, int 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(int u, int par, int 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(int u, int par, int 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(int 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 3064 KB Output is correct
2 Correct 12 ms 3320 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 16416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 6520 KB Output is correct
2 Correct 74 ms 5812 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9080 KB Output is correct
2 Correct 210 ms 7616 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 10580 KB Output is correct
2 Correct 282 ms 10488 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 12580 KB Output is correct
2 Correct 459 ms 12792 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 15524 KB Output is correct
2 Correct 516 ms 13436 KB Output is correct