제출 #98653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98653		user202729	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	12 ms	3072 KiB

uzastopni

#include<iostream>
#include<bitset>
#include<vector>
#include<algorithm>

std::vector<int> val;
std::vector<std::vector<int>> child;

using set=std::bitset<101>;
struct sets{ // half-open range
	set left,right;
};

sets solve(int node){
	sets ans;
	ans.left[val[node]]=1;ans.right[val[node]+1]=1;
	std::vector<int> lnodes,rnodes;
	for(int c:child[node])
		if(val[c]<val[node])
			lnodes.push_back(c);
		else
			rnodes.push_back(c);
	std::sort(begin(lnodes),end(lnodes),[](int a,int b){return val[a]>val[b];});
	std::sort(begin(rnodes),end(rnodes),[](int a,int b){return val[a]<val[b];});
	for(int c:lnodes){
		sets t=solve(c);
		if((t.right&ans.left).any())
			ans.left|=t.left;
	}
	for(int c:rnodes){
		sets t=solve(c);
		if((t.left&ans.right).any())
			ans.right|=t.right;
	}
	return ans;
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int nnode;std::cin>>nnode;
	val.resize(nnode);
	for(int& x:val){
		std::cin>>x;
		--x;
	}
	child.resize(nnode);
	for(int _=nnode-1;_-->0;){
		int a,b;std::cin>>a>>b;--a;--b;
		child[a].push_back(b);
	}

	sets a=solve(0);
	std::cout<<a.left.count()*a.right.count()<<'\n';
}

• Subtask 1: 160 / 160