Submission #99152

# Submission time Handle Problem Language Result Execution time Memory
99152 2019-02-28T21:50:29 Z Shtef Transport (COCI19_transport) C++14
117 / 130
1000 ms 19300 KB
#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[200005], 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]);
		if(dolje[o.x] <= 0){
			sol++;
		}
		b.push_back(dolje[o.x]);
		gore[o.x] = gore[x] + a[o.x] - o.y;
		je[o.x] = (gore[o.x] - maxi >= 0);
		if(je[o.x]){
			sol++;
		}
		b.push_back(gore[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){
		tu[x] = lower_bound(b.begin(), b.end(), gore[x]) - b.begin() + 1;
		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 <= 200001 ; 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');
}

int main(){
sc(n);
for(int i = 1 ; i <= n ; ++i){
	int x;
	sc(x);
	a[i] = x;
}
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;
}
# Verdict Execution time Memory Grader output
1 Correct 15 ms 3200 KB Output is correct
2 Correct 14 ms 3328 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 19 ms 3456 KB Output is correct
2 Correct 25 ms 3760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 214 ms 9856 KB Output is correct
2 Correct 191 ms 9316 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 306 ms 12632 KB Output is correct
2 Correct 329 ms 14064 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 451 ms 16084 KB Output is correct
2 Correct 546 ms 19300 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 202 ms 5784 KB Output is correct
2 Correct 91 ms 5360 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 176 ms 7932 KB Output is correct
2 Correct 347 ms 7612 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 541 ms 9452 KB Output is correct
2 Correct 443 ms 9832 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 875 ms 11364 KB Output is correct
2 Correct 825 ms 11876 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 13944 KB Time limit exceeded
2 Halted 0 ms 0 KB -