oj.uz

답안 #602334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602334 2022-07-22T22:21:11 Z inksamurai Uzastopni (COCI15_uzastopni) C++17
160 / 160
 21 ms 32664 KB 
#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

# 결과 실행 시간 메모리 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