Submission #142643

#	Time	Username	Problem	Language	Result	Execution time	Memory
142643		RafaelSus	Transport (COCI19_transport)	C++17	52 / 130	1069 ms	18292 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1e5 + 5;

int n, a[maxn], w[maxn];
vector <pair<int, long long>> g[maxn];
int used[maxn];

long long dp1[maxn], ben1[maxn];
long long dp2[maxn], ben2[maxn]; 
int sz[maxn];
long long answ;
                         
void sizeCounter(int v, int p){
    sz[v] = 1;       
    dp1[v] = dp2[v] = 0; 
    ben1[v] = ben2[v] = 0;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first;
        if (to == p || used[to]) continue;
        sizeCounter(to, v);      
        sz[v] += sz[to];     
    }                    
}                        
                         
                         
int center = 0;          
void findCen(int v, int p){
	int cnt = sz[v] / 2;
	for (int i = 0; i < g[v].size(); i++){
		int to = g[v][i].first;
		if (to == p || used[to]) continue;
        if (sz[to] >= cnt){
            center = to;
            findCen(to, v);
		}
	}
}

vector <long long> G; 

void push_DP(int v, int p){
	sz[v] = 1;	
	for (int i = 0; i < g[v].size(); i++){
		int to = g[v][i].first;
		int len = g[v][i].second;
		if (to == p || used[to]) continue;

		ben1[to] = ben1[v] + a[v] - len;
		dp1[to] = dp1[v];
		if (ben1[to] < 0){
			dp1[to] -= ben1[to];
			ben1[to] = 0;
		} 	
		
		int d = a[to] - len;
		dp2[to] = dp2[v] + d;
		ben2[to] = min(1ll * d, ben2[v] + d);
		
		push_DP(to, v);
		sz[v] += sz[to];
	}

	if (ben2[v] >= 0){
		G.push_back(dp2[v]);
	}		
}

int findCenter(int v){
	sizeCounter(v, -1);
	center = v;
	findCen(v, -1);
	push_DP(center, -1);	
	return center;
}


vector <long long> P;
vector <int> ver;

void solve(int v, int p){

	if (p != -1){
		ver.push_back(v);
		if (ben2[v] >= 0){
			P.push_back(dp2[v]);	
		}	
	}
		
	int idx = lower_bound(G.begin(), G.end(), dp1[v]) - G.begin();
	answ += (int)G.size() - idx;
	if (p == -1) answ--;
	
	for (int i = 0; i < g[v].size(); i++){
		int to = g[v][i].first;
		if (to == p || used[to]) continue;
		solve (to, v);
		if (p == -1){
			sort (P.begin(), P.end());
			for (int j = 0; j < ver.size(); j++){
				int u = ver[j];
				int id = lower_bound(P.begin(), P.end(), dp1[u]) - P.begin();
				answ -= (int)P.size() - id;	
			}	
			P.clear();
			ver.clear();
		}	
	}
}

void centroidDecomposition() {
	queue <int> q;
	q.push(1);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		v = findCenter(v);
		sort(G.begin(), G.end());
		solve(v, -1);
		G.clear();
		
		for (int i = 0; i < g[v].size(); i++){
			int to = g[v][i].first;
			if (used[to] || sz[to] == 1) continue;
			q.push(to);	
		}
		used[v] = 1;
	}
}



int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 0; i < n - 1; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		g[x].push_back({ y, z });
		g[y].push_back({ x, z });
	}

	centroidDecomposition();
	cout << answ << '\n';
	return 0;
}

Compilation message (stderr)

transport.cpp: In function 'void sizeCounter(int, int)':
transport.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
transport.cpp: In function 'void findCen(int, int)':
transport.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++){
                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void push_DP(int, int)':
transport.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++){
                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void solve(int, int)':
transport.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++){
                  ~~^~~~~~~~~~~~~
transport.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < ver.size(); j++){
                    ~~^~~~~~~~~~~~
transport.cpp: In function 'void centroidDecomposition()':
transport.cpp:126:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < g[v].size(); i++){
                   ~~^~~~~~~~~~~~~

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