Submission #39436

#	Time	Username	Problem	Language	Result	Execution time	Memory
39436		adamczh1	Uzastopni (COCI15_uzastopni)	C++14	0 / 160	0 ms	1840 KiB

uzastopni

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

#define SIZE(x) (int)(x).size()

inline int readi(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int N;
int V[10001];
vector<int> adj[10001];
bitset<101> bs[10001][101]; // possible L for each R
vector<int> s[10001][101];

void dfs(int cur){
	for(int v:adj[cur]){
		dfs(v);
	}
	for(int i=1;i<=100;i++){
		if(i==V[cur]) bs[cur][i].set(i), bs[cur][i]|=bs[cur][i-1];
		for(int v:adj[cur])
			for(int j:s[v][i]){
				bs[cur][i].set(j);
				bs[cur][i]|=bs[cur][j-1];
			}
		for(int j=1;j<=i;j++)
			if(bs[cur][i][j] && V[cur]>=j && V[cur]<=i)
				s[cur][i].push_back(j);
	}
}

int main(){
	N=readi();
	for(int i=1; i<=N; i++){
		V[i]=readi();
	}
	for(int i=1; i<N; i++){
		int A=readi(),B=readi();
		adj[A].push_back(B);
	}
	dfs(1);
	int ans=0;
	for(int r=V[1];r<=100;r++){
		ans+=SIZE(s[1][r]);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 0 / 160