Submission #99153

#	Time	Username	Problem	Language	Result	Execution time	Memory
99153		Shtef	Transport (COCI19_transport)	C++14	130 / 130	792 ms	18216 KiB

Main

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef pair <int, ll> pil;
#define x first
#define y second
#define mp make_pair

ll a[100005], dolje[100005], gore[100005];
vector <pil> ms[100005];
bool bio[100005], je[100005];
int br, ss[100005], tu[100005], tam[100005], f[100005], n;
vector <ll> b;
const ll inf = (ll)1e15;

void dfs1(int x, int p){
	br++;
	ss[x] = 1;
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = (*i).x;
		if(o == p || bio[o])
			continue;
		dfs1(o, x);
		ss[x] += ss[o];
	}
}

int dfs2(int x, int p){
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = (*i).x;
		if(o == p || bio[o])
			continue;
		if(ss[o] > br / 2)
			return dfs2(o, x);
	}
	return x;
}

ll sol;

void initdp(int x, int p, ll sad, ll maxi){
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		pil o = *i;
		if(o.x == p || bio[o.x])
			continue;
		dolje[o.x] = max(sad - a[x] + o.y, dolje[x]);
		sol += (dolje[o.x] <= 0);
		b.push_back(dolje[o.x]);
		gore[o.x] = gore[x] + a[o.x] - o.y;
		je[o.x] = (gore[o.x] - maxi >= 0);
		sol += je[o.x];
		initdp(o.x, x, sad - a[x] + o.y, max(maxi, gore[o.x]));
	}
}

void dfs3(int x, int p){
	if(p != -1){
		if(je[x]){
			tu[x] = upper_bound(b.begin(), b.end(), gore[x]) - b.begin();
		}
		tam[x] = lower_bound(b.begin(), b.end(), dolje[x]) - b.begin() + 1;
	}
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = (*i).x;
		if(o == p || bio[o])
			continue;
		dfs3(o, x);
	}
}

void update(int x, int y){
	for(int i = x ; i <= 100001 ; i += (i & -i)){
		f[i] += y;
	}
}

int sum(int x){
	int ret = 0;
	for( ; x > 0 ; x -= (x & -x)){
		ret += f[x];
	}
	return ret;
}

void dfs4(int x, int p, int add){
	if(p != -1){
		update(tam[x], add);
	}
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = (*i).x;
		if(o == p || bio[o])
			continue;
		dfs4(o, x, add);
	}
}

ll dfs5(int x, int p){
	ll ret = 0;
	if(je[x]){
		ret += sum(tu[x]);
	}
	for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = (*i).x;
		if(o == p || bio[o])
			continue;
		ret += dfs5(o, x);
	}
	return ret;
}

void decompose(int root){
	br = 0;
	dfs1(root, -1);
	int centroid = dfs2(root, -1);
	bio[centroid] = 1;
	dolje[centroid] = -inf;
	gore[centroid] = 0;
	b.clear();
	initdp(centroid, -1, 0, 0);
	b.push_back(0LL);
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	/*
	for(int i = 0 ; i < (int)b.size() ; ++i){
		cout << b[i] << ":";
	}
	cout << " . ";
	*/
	dfs3(centroid, -1);
	dfs4(centroid, -1, 1);
	//cout << centroid << " - ";
	for(vector <pil>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		pil o = *i;
		if(bio[o.x])
			continue;
		dfs4(o.x, centroid, -1);
		sol += dfs5(o.x, centroid);
		//cout << "[" << dfs5(o.x, centroid) << "] ";
		dfs4(o.x, centroid, 1);
	}
	//cout << endl;
	dfs4(centroid, -1, -1);
	for(vector <pil>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		int o = (*i).x;
		if(bio[o])
			continue;
		decompose(o);
	}
}

inline void sc(int &x){
	register int c;
	x = 0;
	do{
		c = getchar();
	}while(c < '0');
	do{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}while(c >= '0');
}

inline void scll(ll &x){
	register int c;
	x = 0;
	do{
		c = getchar();
	}while(c < '0');
	do{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}while(c >= '0');
}

int main(){
sc(n);
for(int i = 1 ; i <= n ; ++i){
	scll(a[i]);
}
for(int i = 0 ; i < n - 1 ; ++i){
	int x, y, w;
	sc(x);
	sc(y);
	sc(w);
	ms[x].push_back(mp(y, w));
	ms[y].push_back(mp(x, w));
}
decompose(1);
printf("%lld\n", sol);

return 0;
}

• 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