oj.uz

Submission #97639

# Submission time Handle Problem Language Result Execution time Memory
97639 2019-02-17T15:32:52 Z JedrzejOlkowski Transport (COCI19_transport) C++14
130 / 130
 820 ms 19996 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct trio{
	ll suma, mindo;
	int v;
};
trio make_trio(ll a, ll b, int c){
	trio wyn;
	wyn.suma=a; wyn.mindo=b; wyn.v=c;
	return wyn;
}


const int N=1e5+50;
const ll I=1000LL*1000LL*1000LL*1000LL*1000LL*1000LL;
vector< pair<int, int> >Kra[N];
int Paliwo[N];
int Rozmiar[N];

int Ojciec[N];
int Odw[N];
int Zaz[N];
int Wynik[N];
vector< trio >Start[N];
vector<ll>Odleglosci;

void WczytajDane(int &n){
	cin>>n; int a, b, c;
	for(int i=1; i<=n; ++i) cin>>Paliwo[i];
	for(int i=1; i<n; i++){
		cin>>a>>b>>c;
		Kra[a].push_back( make_pair(b, c) );
		Kra[b].push_back( make_pair(a, c) );
	}
}

void LiczRozmiar(int v){
	Odw[v]=1; Rozmiar[v]++;
	for(int i=0; i<(int)Kra[v].size(); i++){
		if( Odw[ Kra[v][i].first ]==1 ) continue;
		LiczRozmiar(Kra[v][i].first);
		Ojciec[ Kra[v][i].first ]=v;
		Rozmiar[v]+=Rozmiar[Kra[v][i].first];
	}
}

int LiczCentroid(vector<int> &Aktu){
	int v, czy, s; s=(int)Aktu.size();
	for(int i=0; i<(int)Aktu.size(); i++){
		v=Aktu[i];
		czy=1;
		for(int j=0; j<(int)Kra[v].size(); j++){
			if( Ojciec[ v ]==Kra[v][j].first ) continue;
			if( Rozmiar[ Kra[v][j].first ]>s/2 ) czy=0;			
		}
		if( s-Rozmiar[v]>s/2 ) czy=0;
		if( czy==1 ) return v;
	}
	return 0;
}

bool Porownaj(trio a, trio b){
	if(a.mindo<b.mindo) return 1;
	return 0;
}

int PierwszyWiekszy(ll szukana){
	int p, k, s;
	p=0; k=(int)Odleglosci.size()-1;
	while(p<k){
		s=(p+k)/2;
		if(Odleglosci[s]>=szukana) k=s;
		else					 p=s+1;
	}
	if(Odleglosci[p]<szukana) return 0;
	return (int)Odleglosci.size()-p;
}

int Odejmowanie(ll szukana, int gdzie){
	int p, k, s;
	p=0; k=(int)Start[gdzie].size()-1;
	while(p<k){
		s=(p+k)/2;
		if(Start[gdzie][s].mindo>=szukana) k=s;
		else					 p=s+1;
	}
	if(Start[gdzie][p].mindo<szukana) return 0;
	return (int)Start[gdzie].size()-p;
}

void LiczWyniki(int aktu){
	//cout << "LICZE " << Kra[2][aktu].first << endl;
	for(int i=0; i<(int)Start[aktu].size(); i++){
		if( Start[aktu][i].v==-1 ) continue;
	//	cout << "licze " << Start[aktu][i].v << " " << Start[aktu][i].suma << endl;
	//	cout << "ile wiekszych " << PierwszyWiekszy(-Start[aktu][i].suma) << endl;
	//	cout << "ile odejmuje " << Odejmowanie(-Start[aktu][i].mindo, aktu) << endl;
	//	if( Start[aktu][i].v==5 ) cout << "dodaej " << (PierwszyWiekszy(-Start[aktu][i].suma)-Odejmowanie(-Start[aktu][i].suma, aktu)+1) << endl;
		Wynik[ Start[aktu][i].v ]+=(PierwszyWiekszy(-Start[aktu][i].suma)-Odejmowanie(-Start[aktu][i].suma, aktu)+1);
	}
}

void LiczAktu(int v, vector<int> &Dod){
	Odw[v]=1; Dod.push_back(v);
	for(int i=0; i<(int)Kra[v].size(); i++){
		if(Odw[ Kra[v][i].first ]==0) LiczAktu(Kra[v][i].first, Dod);
	}
}


void LiczWynikWrzucOdleglosci(int v, int gdzie_wyn, ll suma, ll mini_do, ll mini_od, int k){
//	cout << "v " << v << endl;
//	cout << "mini_do " << mini_do << endl;
//	cout << "roznica " << (ll)Paliwo[v] << endl;
//	cout << "lacznie " << mini_do+(ll)Paliwo[v] << endl; 
	if(mini_do>=0LL){
		Wynik[gdzie_wyn]++;
//		if(gdzie_wyn==5) cout << "dodaje " << v << endl;
	}
	//cout << "mini_do " << v << " : " << mini_do << endl;
	//if( gdzie_wyn==5 ) cout << "dodaje do 5 " << v << " : " << mini_do << endl;
	Odleglosci.push_back( mini_do ); Odw[v]=1;
	ll mini, mini2;
//	cout << v << ": " << mini_od << endl;
	if(mini_od<0LL) Start[k].push_back( make_trio( suma-(ll)Paliwo[gdzie_wyn]+(ll)Paliwo[v], mini_do, -1 ) );
	else		      Start[k].push_back( make_trio( suma-(ll)Paliwo[gdzie_wyn]+(ll)Paliwo[v], mini_do, v ) );
	//cout << "vS " << v << " " << mini_do <<  endl;
	for(int i=0; i<(int)Kra[v].size(); i++){
		if( Odw[ Kra[v][i].first ]==1 ) continue;
		mini=min(mini_do, suma+(ll)Paliwo[v]-(ll)Kra[v][i].second);
		mini2=min(-(ll)Kra[v][i].second+(ll)Paliwo[Kra[v][i].first], mini_od-(ll)Kra[v][i].second+(ll)Paliwo[Kra[v][i].first]);
		LiczWynikWrzucOdleglosci(Kra[v][i].first, gdzie_wyn, suma+(ll)Paliwo[v]-(ll)Kra[v][i].second, mini, mini2, k);
	}
}


void LiczCentroid(int v){
	vector<int>Aktu;
	LiczAktu(v, Aktu);
	if( (int)Aktu.size()==1 ) return;
	for(int i=0; i<(int)Aktu.size(); i++) Odw[Aktu[i]]=Zaz[Aktu[i]];
	LiczRozmiar(Aktu[0]);
	int c=LiczCentroid(Aktu);
	Zaz[c]=1;
	for(int i=0; i<(int)Aktu.size(); i++){
		Ojciec[Aktu[i]]=Rozmiar[ Aktu[i] ]=0;
		Odw[Aktu[i]]=Zaz[Aktu[i]];
	}
	//cout << endl;
//	cout << "CENTROID " << c << endl;
	for(int i=0; i<(int)Kra[c].size(); i++){
		if( Zaz[ Kra[c][i].first ]==1 ) continue;
		LiczWynikWrzucOdleglosci(Kra[c][i].first, c, (ll)Paliwo[c]-(ll)Kra[c][i].second, (ll)Paliwo[c]-(ll)Kra[c][i].second, -(ll)Kra[c][i].second+(ll)Paliwo[ Kra[c][i].first ], i);
		sort( Start[i].begin(), Start[i].end(), Porownaj );
	}
	for(int i=0; i<(int)Aktu.size(); i++) Odw[Aktu[i]]=Zaz[Aktu[i]];
//	cout << "ODLEGLOSCI " << endl;
	sort(Odleglosci.begin(), Odleglosci.end());
//	for(int i=0; i<(int)Odleglosci.size(); i++) cout << Odleglosci[i] << " ";
//	cout << endl;
	for(int i=0; i<(int)Kra[c].size(); i++){
		if( Zaz[ Kra[c][i].first ]==1 ) continue;
//		cout << "START KORZEEN " << Kra[c][i].first << endl;
	//	for(int j=0; j<(int)Start[i].size(); j++) cout << Start[i][j].suma << " " << Start[i][j].mindo << " " << Start[i][j].v << endl;
	}
	//cout << "licze " << c << endl;
	for(int i=0; i<(int)Kra[c].size(); i++){
		if( Zaz[ Kra[c][i].first ]==0 ) LiczWyniki(i);
		Start[i].clear();
	}
	Odleglosci.clear();
	for(int i=0; i<(int)Kra[c].size(); i++){
		if( Zaz[ Kra[c][i].first ]==0 )	LiczCentroid( Kra[c][i].first );
	}
	
	
}

int main (){
	int n; ll suma=0LL;
	WczytajDane(n);
	LiczCentroid(1);
	//for(int i=1; i<=n; i++) cout << i << " : " << Paliwo[i] << endl;
	//for(int i=1; i<=n; i++) cout << i << ": " << Wynik[i] << endl;
	for(int i=1; i<=n; i++) suma+=(ll)Wynik[i];
	cout<<suma<<"\n";
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5376 KB Output is correct
2 Correct 16 ms 5632 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5632 KB Output is correct
2 Correct 22 ms 5888 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 11660 KB Output is correct
2 Correct 186 ms 11000 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 13992 KB Output is correct
2 Correct 280 ms 15720 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 17440 KB Output is correct
2 Correct 427 ms 19996 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 8348 KB Output is correct
2 Correct 89 ms 8460 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 11584 KB Output is correct
2 Correct 257 ms 9928 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 12216 KB Output is correct
2 Correct 378 ms 12148 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 14452 KB Output is correct
2 Correct 560 ms 15096 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 17364 KB Output is correct
2 Correct 579 ms 15860 KB Output is correct