oj.uz

답안 #405524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405524 2021-05-16T14:00:04 Z codebuster_10 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 480 ms 13508 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 
#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
 
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue
 
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
 
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}
 
const int MAX_N = 10000, MAX_V = 105;
//bitset<MAX_N> ans[MAX_V][MAX_V]; 
bitset<MAX_V> dp1[MAX_V], dp2[MAX_V], EMPTY;// dp1 without rev, dp2 with rev
vt<pr<int,int>> P[MAX_N];
signed main(){
  setIO();
  int n; rd(n);
  vt<int> v(n); rd(v);
  f(i,0,n) --v[i];
  vt<int> g[n];
  f(_,0,n-1){
  	int a,b; rd(a,b); --a,--b;
  	g[a].pb(b);
  }
  function<void(int)> dfs = [&](int i){
  	for(auto j : g[i])	dfs(j);
  	f(j,0,MAX_V) dp1[j] = dp2[j] = EMPTY;
  	for(auto j : g[i]){
  		for(auto [L,R] : P[j]){
  			if(R <= v[i] || v[i] < L){
  				dp1[L][R] = true;
  				dp2[R][L] = true;
  			}
  		}
  	}
  	dp1[v[i]][v[i]+1] = true;
  	//ans[v[i]][v[i]+1][i] = true;
  	P[i].pb({v[i],v[i]+1});
		dp2[v[i]+1][v[i]] = true;
  	for(int len = 1; len < MAX_V; ++len){
  		for(int L = 0; L + len < MAX_V; ++L){
  			int R = L + len;
  			int res = (dp1[L]&dp2[R]).count();
  			if(res){
  				dp1[L][R] = true;
  				if(dp1[L][R] && L <= v[i] && v[i] < R){
  					//ans[L][R][i] = true;	
  					P[i].pb({L,R});
  				}
  				dp2[R][L] = true;
  			}
  		}
  	}
  	return;
  };
  dfs(0);
  cout << sz(P[0]);
}

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 556 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 6 ms 588 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 7 ms 460 KB Output is correct
11 Correct 432 ms 1436 KB Output is correct
12 Correct 407 ms 1348 KB Output is correct
13 Correct 397 ms 1348 KB Output is correct
14 Correct 474 ms 13508 KB Output is correct
15 Correct 480 ms 13428 KB Output is correct
16 Correct 429 ms 13500 KB Output is correct
17 Correct 403 ms 1392 KB Output is correct
18 Correct 437 ms 1448 KB Output is correct
19 Correct 455 ms 5668 KB Output is correct
20 Correct 415 ms 5592 KB Output is correct