Submission #1103402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103402		codexistent	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	19 ms	5972 KiB

uzastopni

// testing

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
 
const int mxn = 1e4+10;
 
int N;
int arr[mxn];
vector<int> tree[mxn];
vector<int> lp[mxn],rp[mxn];
vector<int> lop[110],rop[110];
bitset<110> dl,dr;
 
void dfs(int now){
	for(auto nxt:tree[now]){
		dfs(nxt);
	}
	for(auto &i:lop)i.clear();
	for(auto &i:rop)i.clear();
	for(auto nxt:tree[now]){
		for(auto &i:lp[nxt]){
			for(auto &j:rp[nxt]){
				assert(i<=j);
				if(i>arr[now])rop[i].push_back(j);
				if(j<arr[now])lop[j].push_back(i);
			}
		}
	}
	dl.reset();
	dr.reset();
	dl[arr[now]] = dr[arr[now]] = 1;
	for(int i = arr[now];i+1<110;i++){
		if(dr[i]){
			rp[now].push_back(i);
			for(auto &j:rop[i+1])dr[j] = 1;
		}
	}
	for(int i = arr[now];i>0;i--){
		if(dl[i]){
			lp[now].push_back(i);
			for(auto &j:lop[i-1])dl[j] = 1;
		}
	}
	return;
}
 
int main(){
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
	}
	dfs(1);

	cout<<(lp[1].size())*(rp[1].size())<<endl;
}

• Subtask 1: 160 / 160