oj.uz

답안 #380577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380577 2021-03-22T11:26:15 Z GioChkhaidze Transport (COCI19_transport) C++14
130 / 130
 352 ms 48780 KB 
#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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5740 KB Output is correct
2 Correct 9 ms 5612 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 6252 KB Output is correct
2 Correct 13 ms 7020 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 22884 KB Output is correct
2 Correct 84 ms 22756 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 26980 KB Output is correct
2 Correct 153 ms 35292 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 40668 KB Output is correct
2 Correct 232 ms 48780 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 12184 KB Output is correct
2 Correct 46 ms 8376 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 11236 KB Output is correct
2 Correct 130 ms 16400 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 16868 KB Output is correct
2 Correct 194 ms 15572 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 336 ms 21348 KB Output is correct
2 Correct 284 ms 19164 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 352 ms 36196 KB Output is correct
2 Correct 342 ms 33628 KB Output is correct