oj.uz

Submission #99131

# Submission time Handle Problem Language Result Execution time Memory
99131 2019-02-28T19:47:02 Z Shtef Transport (COCI19_transport) C++14
0 / 130
 979 ms 18348 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

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

int n, br, ss[100005], f[200005], tam[100005], tu[100005];
ll a[100005], gore[100005], dolje[100005];
vector <pil> ms[100005];
bool bio[100005], je[100005];
vector <ll> b;

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;
}


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

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

void initdp(int x, int p, ll sad, ll cur, ll maxi){
	b.push_back(gore[x]);
	b.push_back(dolje[x]);
	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(dolje[x], sad + o.y);
		gore[o.x] = cur + a[o.x] - o.y;
		je[o.x] = (gore[o.x] - maxi >= 0);
		initdp(o.x, x, sad - a[x] + o.y, cur + a[o.x] - o.y, max(maxi, gore[o.x]));
	}
}

void dfs3(int x, int p, int add){
	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;
		dfs3(o, x, add);
	}
}

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

void dfs5(int x, int p){
	tam[x] = lower_bound(b.begin(), b.end(), dolje[x]) - b.begin() + 1;
	tu[x] = lower_bound(b.begin(), b.end(), gore[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;
		dfs5(o, x);
	}
}

ll sol;

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

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.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;
	ll w;
	cin >> x >> y >> w;
	ms[x].push_back(mp(y, w));
	ms[y].push_back(mp(x, w));
}
decompose(1);
cout << sol << endl;

return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 11084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 14252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 18348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 6544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 9032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 11288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 705 ms 13688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 979 ms 16696 KB Output isn't correct
2 Halted 0 ms 0 KB -