oj.uz

답안 #97538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97538 2019-02-16T21:39:44 Z IgorBaliuk Transport (COCI19_transport) C++14
130 / 130
 365 ms 13996 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define endl "\n"
#define mt make_tuple
#define mp make_pair

template <typename T1, typename T2>
bool umax(T1 &a, const T2&b) { return a < b ? a = b, 1 : 0;}
template <typename T1, typename T2> 
bool umin(T1 &a, const T2 &b) {return a > b ? a = b, 1 : 0;}
template <typename T>
T sqr(T a) {return a * a;}

mt19937 rng(20010709);
const int mod = 1000000007;
const int INF = 1000000001;
const ll INFLL = INF;
const int N = 100005;
const int M = 17;

struct Centroid {
	int n, t;
	vector <vector <pii>> e;
	vector <int> locked, a, len;
	vector <ll> globalUp, globalDown, localUp, localDown;
	ll result;

	Centroid() { }
	void init(int N) {
		n = N;
		e.assign(n + 1, vector <pii>());
		locked.assign(n + 1, 0);
		a.assign(n + 1, 0);
		len.assign(n + 1, 0);
		result = 0;
	}

	int dfsLen(int v, int p = -1) {
		len[v] = 1;

		for (auto it : e[v]) {
			if (!locked[it.first] && (it.first != p))
				len[v] += dfsLen(it.first, v);
		}

		return len[v];
	}

	int findCentroid(int v) {
		int p = -1, found = 1, fullLen = len[v];

		while (found) {
			found = 0;

			for (auto it : e[v]) {
				if (!locked[it.first] && (it.first != p) && (len[it.first] * 2 >= fullLen)) {
					p = v;
					v = it.first;
					found = 1;
					break;
				}
			}
		}

		return v;
	}

	void process(vector <ll> &up, vector <ll> &down, int d = 1) {
		sort(up.begin(), up.end());
		sort(down.begin(), down.end());

		for (int i = 0, j = 0; i < down.size(); i++) {
			while ((j < up.size()) && (up[j] < down[i]))
				j++;

			result += d * (1LL * up.size() - j);
		}
	}

	void dfs(int v, int p, ll up, ll maxUp, ll down, ll maxDown) {
		umax(maxDown, -down);
		up += a[v];
		down += a[v];

		if (a[v] >= maxUp)
			localUp.push_back(up);

		localDown.push_back(maxDown);

		for (auto it : e[v]) {
			if (!locked[it.first] && (it.first != p))
				dfs(it.first, v, up - it.second, it.second + max(0LL, maxUp - a[v]), down - it.second, maxDown);
		}
	}

	void get(int v) {
		dfsLen(v);
		v = findCentroid(v);
		t = a[v];

		globalUp.clear();
		globalDown.clear();
		globalUp.push_back(0);
		globalDown.push_back(-a[v]);
		result--;

		for (auto it : e[v]) {
			if (!locked[it.first]) {
				localUp.clear();
				localDown.clear();

				dfs(it.first, v, -it.second, it.second, (a[v] - it.second), 0);

				process(localUp, localDown, -1);
				globalUp.insert(globalUp.end(), localUp.begin(), localUp.end());
				globalDown.insert(globalDown.end(), localDown.begin(), localDown.end());
			}
		}

		process(globalUp, globalDown);

		locked[v] = 1;

		for (auto it : e[v]) {
			if (!locked[it.first])
				get(it.first);
		}
	}

	ll solve() {
		get(1);
		return result;
	}
};

int n;
Centroid c;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	cin >> n;

	c.init(n);

	for (int i = 1; i <= n; i++)
		cin >> c.a[i];

	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		c.e[u].push_back({ v, w });
		c.e[v].push_back({ u, w });
	}

    cout << c.solve() << endl;

    return 0;
}

Compilation message

transport.cpp: In member function 'void Centroid::process(std::vector<long long int>&, std::vector<long long int>&, int)':
transport.cpp:84:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0, j = 0; i < down.size(); i++) {
                          ~~^~~~~~~~~~~~~
transport.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while ((j < up.size()) && (up[j] < down[i]))
            ~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 6 ms 768 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 896 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 6620 KB Output is correct
2 Correct 65 ms 5760 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 8708 KB Output is correct
2 Correct 113 ms 9688 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 11772 KB Output is correct
2 Correct 180 ms 13996 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 3044 KB Output is correct
2 Correct 44 ms 2656 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 4856 KB Output is correct
2 Correct 113 ms 4128 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 5860 KB Output is correct
2 Correct 214 ms 6268 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 7588 KB Output is correct
2 Correct 287 ms 7980 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 365 ms 9788 KB Output is correct
2 Correct 266 ms 8728 KB Output is correct