Submission #380577

#	Time	Username	Problem	Language	Result	Execution time	Memory
380577		GioChkhaidze	Transport (COCI19_transport)	C++14	130 / 130	352 ms	48780 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 1e5 + 5;

ll ans;
bool f[N];
int n, P, C, a[N];
vector < ll > s[N];
vector < pair < int , int > > v[N];

int get(int x, ll u) {
	int l = 0, r = s[x].size() - 1, mid, res = 0;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (u + s[x][mid] >= 0) 
			res = s[x].size() - mid, r = mid - 1;
				else
			l = mid + 1; 
	}
	return res;
}

int find_center(int x, int p, int &cen, int num) {
	int tot = 1;
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i].F;
		if (f[to] || to == p) continue;
 		tot += find_center(to, x, cen, num);
	}
	if (cen == -1 && (2 * tot >= num || x == p)) cen = x;
	return tot;
}

void fromc(int x, int p, ll recm, ll rec) {
	if (recm >= 0) ++ans;		
	s[P].push_back(recm);
	s[C].push_back(recm);
	for (int i = 0; i < v[x].size(); ++i) {
		ll to = v[x][i].F, cost = a[x] - v[x][i].S;
		if (f[to] || to == p) continue;
		fromc(to, x, min(recm, rec + cost), rec + cost);
	}
}

void ansc(int x, int p, ll recm, ll rec) {
	if (recm >= 0) {
		ans += get(C, rec) - get(P, rec);
		++ans;
	}
	for (int i = 0; i < v[x].size(); ++i) {
		ll to = v[x][i].F, cost = a[to] - v[x][i].S;
		if (f[to] || to == p) continue;
		ansc(to, x, min(recm + cost, cost), rec + cost);
	}
}

void Centroid(int x, int num) {
	int cen = -1;
	find_center(x, x, cen, num);
	f[cen] = true;
	C = cen;
	for (int i = 0; i < v[cen].size(); ++i) {
		ll to = v[cen][i].F, cost = a[cen] - v[cen][i].S; P = to;
		if (f[to]) continue;
		fromc(to, cen, cost, cost);
		sort(s[to].begin(), s[to].end());
	}

	sort(s[cen].begin(), s[cen].end());	
	for (int i = 0; i < v[cen].size(); ++i) {
		ll to = v[cen][i].F, cost = a[to] - v[cen][i].S; P = to;
		if (f[to]) continue;	
		ansc(to, cen, cost, cost);
	}
	
	s[cen].clear();
	for (int i = 0; i < v[cen].size(); ++i) {
		int to = v[cen][i].F;
		if (f[to]) continue;
		s[to].clear();
		Centroid(to, num / 2);
	}
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i < n; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].pb({b, c});
		v[b].pb({a, c});
	}
	
	Centroid(1, n);
	cout << ans << "\n";	
}

Compilation message (stderr)

transport.cpp: In function 'int find_center(int, int, int&, int)':
transport.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void fromc(int, int, long long int, long long int)':
transport.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void ansc(int, int, long long int, long long int)':
transport.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void Centroid(int, int)':
transport.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp: At global scope:
transport.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main () {
      |       ^

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13