oj.uz

답안 #602328

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

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(n,vec(bitset<100>)(100)),evsr;
	evsr=evsl;
	vi usd(100,0);
	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[u][i];
				}
			}
		}
		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[u][i];
				}
			}
		}
		// if(v==2){
		// 	print(tmpr,"hi");
		// }
		for(int i=0;i<100;i++){
			if(tmpr[i]){
				evsl[v][i]|=tmpl;
			}
			if(tmpl[i]){
				evsr[v][i]|=tmpr;
			}
		}
		usd[a[v]]=0;
	};
	dfs(dfs,0,-1);
	int res=0;
	for(int i=0;i<100;i++){
		if(evsl[0][i].count()){
			// print(i,evsl[0][i]);
			res+=evsl[0][i].count();
		}
	}
	print(res);
}

Subtask #1
80.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 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 1 ms 596 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 0 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Runtime error 18 ms 33108 KB Memory limit exceeded
12 Runtime error 16 ms 33108 KB Memory limit exceeded
13 Runtime error 17 ms 33132 KB Memory limit exceeded
14 Runtime error 22 ms 33104 KB Memory limit exceeded
15 Runtime error 16 ms 33100 KB Memory limit exceeded
16 Runtime error 17 ms 33060 KB Memory limit exceeded
17 Runtime error 17 ms 33096 KB Memory limit exceeded
18 Runtime error 17 ms 33096 KB Memory limit exceeded
19 Runtime error 17 ms 33112 KB Memory limit exceeded
20 Runtime error 16 ms 33104 KB Memory limit exceeded