Submission #527338

#	Time	Username	Problem	Language	Result	Execution time	Memory
527338		colazcy	Uzastopni (COCI15_uzastopni)	C++11	160 / 160	6 ms	2000 KiB

uzastopni

#include <cstdio>
#include <cassert>
#include <vector>
#include <bitset>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e4 + 10,maxm = 103;

std::bitset<maxm> L[maxn],R[maxn];
int n,val[maxn];
std::vector<int> G[maxn];
void dp(const int u){
	L[u].set(val[u]);
	R[u].set(val[u]);
	for(let v : G[u])dp(v);
	
	std::sort(G[u].begin(),G[u].end(),[](const int x,const int y){return val[x] < val[y];});
	for(let v : G[u])
		if(val[v] > val[u] && ((R[u] << 1) & L[v]).any())R[u] |= R[v];
	std::reverse(G[u].begin(),G[u].end());
	for(let v : G[u])
		if(val[v] < val[u] && ((L[u] >> 1) & R[v]).any())L[u] |= L[v];
}
int main(){
	// std::freopen("uzastopni.in","r",stdin);
	// std::freopen("uzastopni.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,1,n)std::scanf("%d",val + i);
	repn(n - 1){
		int u,v; std::scanf("%d %d",&u,&v);
		G[u].push_back(v);
	}
	dp(1);
	std::printf("%d\n",(int)(L[1].count() * R[1].count()));
	// std::fclose(stdin);
	// std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:33:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
uzastopni.cpp:34:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  rep(i,1,n)std::scanf("%d",val + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
uzastopni.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   int u,v; std::scanf("%d %d",&u,&v);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 160 / 160