oj.uz

Submission #405495

# Submission time Handle Problem Language Result Execution time Memory
405495 2021-05-16T13:21:21 Z codebuster_10 Uzastopni (COCI15_uzastopni) C++17
80 / 160
 500 ms 8900 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
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]){
  		f(L,0,MAX_V){
  			f(R,L+1,MAX_V){
  				if(ans[L][R][j] && (R <= v[i] || v[i] < L)){
  					dp1[L][R] = true;
  					dp2[R][L] = true;
  				}
  			}
  		}
  	}
  	dp1[v[i]][v[i]+1] = true;
		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;
  				dp2[R][L] = true;
  			}
  		}
  	}
  	f(L,0,MAX_V){
  		f(R,L+1,MAX_V){
  			if(dp1[L][R] && L <= v[i] && v[i] < R){
  				ans[L][R][i] = true;	
  			}
  		}
  	}
  	return;
  };
  dfs(0);
  int out = 0;
  f(L,0,MAX_V){
  	f(R,L+1,MAX_V){
  		if(ans[L][R][0]){
  			++out;
  		}
  	}
  }
  cout << out;
}

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 6 ms 320 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 7 ms 320 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 10 ms 2236 KB Output is correct
7 Correct 9 ms 2508 KB Output is correct
8 Correct 10 ms 3020 KB Output is correct
9 Correct 9 ms 840 KB Output is correct
10 Correct 9 ms 844 KB Output is correct
11 Execution timed out 670 ms 1144 KB Time limit exceeded
12 Execution timed out 688 ms 1100 KB Time limit exceeded
13 Execution timed out 667 ms 984 KB Time limit exceeded
14 Execution timed out 725 ms 8744 KB Time limit exceeded
15 Execution timed out 820 ms 8656 KB Time limit exceeded
16 Execution timed out 718 ms 8900 KB Time limit exceeded
17 Execution timed out 699 ms 1112 KB Time limit exceeded
18 Execution timed out 675 ms 980 KB Time limit exceeded
19 Execution timed out 680 ms 4676 KB Time limit exceeded
20 Execution timed out 681 ms 4548 KB Time limit exceeded