Cod sursa(job #2607105)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 29 aprilie 2020 11:35:14
Problema Guvern Scor 100
Compilator cpp-64 Status done
Runda why Marime 1.86 kb
	
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int SIZE = 200002;
 
typedef vector<int> VI;
typedef vector<pair<int, int> > VP;
 
int N, result;
VI V[SIZE], T[SIZE];
VP aux;
int val[SIZE], P[SIZE], pos[SIZE], where[SIZE], pnow;
int D[SIZE];
bool S[SIZE];
 
class set_compare
{
	public:
		bool operator () (const int& i1, const int& i2)
		{
			return i1 < i2;
		}
};
set<int, set_compare> Set;
 
inline int compare(const int& i1, const int& i2)
{
	return val[i1] < val[i2];
}
 
void compM(int x)
{
	S[x] = true;
	pos[x] = ++pnow;
	
	set<int, set_compare>::iterator Aval = Set.lower_bound(val[x]);
	int value = P[(Aval == Set.end() ? 0 : *Aval)];
	where[x] = value;
	
	Set.insert(val[x]);
	
	for (VI::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
			compM(*it);
	
	Set.erase(Set.find(val[x]));
}
void Dfs(int x)
{
	S[x] = true;
	for (VI::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
			Dfs(*it);
	
	D[x] = 1;
	if (!T[x].empty())
		for (VI::iterator it = T[x].begin(); it != T[x].end(); ++it)
			D[x] += D[*it];
	
	int tat = where[x], snow = 0;
	while (!T[tat].empty() && pos[x] < pos[T[tat].back()]) // x ii este tata lui T[tat].back()
	{
		snow += D[T[tat].back()];
		T[tat].pop_back();
	}
	
	D[x] = max(D[x], snow);
	T[tat].push_back(x);
}
 
int main()
{
	ifstream fin("guvern.in");
	ofstream fout("guvern.out");
	
	fin >> N;
	for (int i = 1, nod1, nod2; i < N; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
		V[nod2].push_back(nod1);
	}
	for (int i = 1; i <= N; ++i)
	{
		fin >> val[i];
		P[i] = i;
	}
	
	sort(P + 1, P + N + 1, compare);
	for (int i = 1; i <= N; ++i)
		val[P[i]] = i;
	compM(1);
	
	memset(S, 0, sizeof(S));
	Dfs(1);
	
	for (int i = 1; i <= N; ++i)
		result = max(result, D[i]);
	fout << result;
	
	fin.close();
	fout.close();
}