Submission #602334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602334	2022-07-22T22:21:11 Z	inksamurai	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	21 ms	32664 KB

uzastopni

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=(c);i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3aFGabX ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

// bitset<100> usd,evsl[10000][100],evsr[10000][100];

signed main(){
_3aFGabX;
	int n;
	cin>>n;
	vi a(n);
	rep(i,n){
		cin>>a[i];
		a[i]-=1;
	}
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vec(vec(bitset<100>)) evsl(100,vec(bitset<100>)(n)),evsr;
	evsr=evsl;
	bitset<100> usd;
	auto dfs=[&](auto self,int v,int par)->void{
		// if(v==2) print("hi");
		vi ls,rs;
		bitset<100> tmpl,tmpr;
		usd[a[v]]=1;
		// print(v,a[v],usd[4]);
		for(auto &u:adj[v]){
			if(u==par or usd[a[u]]) continue;
			self(self,u,v);
			if(a[u]<a[v]){
				// goes left
				ls.pb(u); 
			}else{
				// goes right
				rs.pb(u);
			}
		}
		// print(sz(ls));
		// please don't tle because of this
		tmpl=0;
		tmpl[a[v]]=1;
		for(int i=a[v]-1;i>=0;i--){
			if(tmpl[i+1]){
				for(auto &u:ls){
					tmpl|=evsl[i][u];
				}
			}
		}
		tmpr=0;
		tmpr[a[v]]=1;
		for(int i=a[v]+1;i<100;i++){
			if(tmpr[i-1]){
				for(auto &u:rs){
					// if(v==0) print(u,evsr[u][i]);
					tmpr|=evsr[i][u];
				}
			}
		}
		// if(v==2){
		// 	print(tmpr,"hi");
		// }
		for(int i=0;i<100;i++){
			if(tmpr[i]){
				evsl[i][v]|=tmpl;
			}
			if(tmpl[i]){
				evsr[i][v]|=tmpr;
			}
		}
		usd[a[v]]=0;
	};
	dfs(dfs,0,-1);
	int res=0;
	for(int i=0;i<100;i++){
		if(evsl[i][0].count()){
			// print(i,evsl[0][i]);
			res+=evsl[i][0].count();
		}
	}
	print(res);
}

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	0 ms	468 KB	Output is correct
5	Correct	0 ms	596 KB	Output is correct
6	Correct	0 ms	596 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	17 ms	32576 KB	Output is correct
12	Correct	16 ms	32564 KB	Output is correct
13	Correct	16 ms	32492 KB	Output is correct
14	Correct	18 ms	32524 KB	Output is correct
15	Correct	17 ms	32564 KB	Output is correct
16	Correct	21 ms	32524 KB	Output is correct
17	Correct	19 ms	32504 KB	Output is correct
18	Correct	16 ms	32564 KB	Output is correct
19	Correct	16 ms	32664 KB	Output is correct
20	Correct	15 ms	32600 KB	Output is correct