답안 #99152 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99152	2019-02-28T21:50:29 Z	Shtef	Transport (COCI19_transport)	C++14	117 / 130	1000 ms	19300 KB

transport

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

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	3200 KB	Output is correct
2	Correct	14 ms	3328 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	3456 KB	Output is correct
2	Correct	25 ms	3760 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	9856 KB	Output is correct
2	Correct	191 ms	9316 KB	Output is correct

Subtask #4
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	306 ms	12632 KB	Output is correct
2	Correct	329 ms	14064 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	451 ms	16084 KB	Output is correct
2	Correct	546 ms	19300 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	202 ms	5784 KB	Output is correct
2	Correct	91 ms	5360 KB	Output is correct

Subtask #7
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	176 ms	7932 KB	Output is correct
2	Correct	347 ms	7612 KB	Output is correct

Subtask #8
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	541 ms	9452 KB	Output is correct
2	Correct	443 ms	9832 KB	Output is correct

Subtask #9
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	875 ms	11364 KB	Output is correct
2	Correct	825 ms	11876 KB	Output is correct

Subtask #10
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1008 ms	13944 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #99152

Compilation message