답안 #96723 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96723	2019-02-11T14:54:12 Z	polyfish	Transport (COCI19_transport)	C++14	78 / 130	700 ms	16416 KB

transport

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

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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	16 ms	3448 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	200 ms	10232 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	253 ms	12636 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	375 ms	16416 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
13.0 / 13.0

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

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

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	700 ms	15524 KB	Output is correct
2	Correct	516 ms	13436 KB	Output is correct

답안 #96723

Compilation message