oj.uz

답안 #405520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405520 2021-05-16T13:55:18 Z codebuster_10 Uzastopni (COCI15_uzastopni) C++17
40 / 160
 482 ms 65536 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>> possible[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],par(n);
  f(_,0,n-1){
  	int a,b; rd(a,b); --a,--b;
  	g[a].pb(b);
  	par[b] = a;
  }
  par[0] = 0;
  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]:possible[j]){
  			dp1[L][R] = true;
  			if(i != 0 && (R <= v[par[i]] || v[par[i]] < L) ){
  				possible[i].pb({L,R});
  			}
  			dp2[R][L] = true;
  		}
  	}
  	dp1[v[i]][v[i]+1] = true;
  	if(i != 0 && (v[i]+1 <= v[par[i]] || v[par[i]] < v[i]) ){
  		possible[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;	
  				}
  				if(i != 0 && (R <= v[par[i]] || v[par[i]] < L) ){
  					possible[i].pb({L,R});
  				}
  				dp2[R][L] = true;
  			}
  		}
  	}
  	return;
  };
  dfs(0);
  int out = 0;
  f(L,0,MAX_V){
  	f(R,L+1,MAX_V){
  		if(dp1[L][R] && L <= v[0] && v[0] < R){
  			++out;
  		}
  	}
  }
  cout << out;
}

Subtask #1
40.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Incorrect 4 ms 716 KB Output isn't correct
3 Incorrect 4 ms 588 KB Output isn't correct
4 Incorrect 4 ms 588 KB Output isn't correct
5 Incorrect 5 ms 588 KB Output isn't correct
6 Incorrect 35 ms 23424 KB Output isn't correct
7 Incorrect 23 ms 16368 KB Output isn't correct
8 Incorrect 27 ms 21816 KB Output isn't correct
9 Correct 5 ms 844 KB Output is correct
10 Correct 6 ms 972 KB Output is correct
11 Incorrect 433 ms 4668 KB Output isn't correct
12 Incorrect 434 ms 3548 KB Output isn't correct
13 Correct 482 ms 2476 KB Output is correct
14 Runtime error 112 ms 65536 KB Execution killed with signal 9
15 Runtime error 110 ms 65536 KB Execution killed with signal 9
16 Runtime error 110 ms 65536 KB Execution killed with signal 9
17 Correct 426 ms 2572 KB Output is correct
18 Correct 435 ms 2456 KB Output is correct
19 Incorrect 462 ms 21808 KB Output isn't correct
20 Incorrect 467 ms 24048 KB Output isn't correct