oj.uz

Submission #527338

# Submission time Handle Problem Language Result Execution time Memory
527338 2022-02-17T08:57:08 Z colazcy Uzastopni (COCI15_uzastopni) C++11
160 / 160
 6 ms 2000 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 524 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 524 KB Output is correct
7 Correct 1 ms 520 KB Output is correct
8 Correct 1 ms 516 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct
12 Correct 6 ms 1104 KB Output is correct
13 Correct 5 ms 1044 KB Output is correct
14 Correct 4 ms 1932 KB Output is correct
15 Correct 4 ms 2000 KB Output is correct
16 Correct 4 ms 2000 KB Output is correct
17 Correct 4 ms 1044 KB Output is correct
18 Correct 4 ms 1104 KB Output is correct
19 Correct 3 ms 920 KB Output is correct
20 Correct 3 ms 904 KB Output is correct