oj.uz

Submission #91874

# Submission time Handle Problem Language Result Execution time Memory
91874 2018-12-30T20:26:32 Z sjhuang26 Uzastopni (COCI15_uzastopni) C++14
160 / 160
 113 ms 8316 KB 
#include<iostream>
#include<bitset>
#include<vector>
using namespace std;
typedef pair<int,int>ii;
int N,a[10000];
const int M=100;
vector<int>t[10000];
bitset<100>f[101];//100+1
vector<ii>d[10000];
vector<int>g[100];
void dfs(int u){
  for(int v:t[u])dfs(v);
  for(int i=0;i<M;++i)g[i].clear();
  for(int i=0;i<M+1;++i)f[i].reset();
  for(int v:t[u]){
    for(ii x:d[v])g[x.first].push_back(x.second);
  }
  for(int i=M-1;i>=0;--i){
    if(i==a[u]){
      f[i]|=f[i+1];
      f[i].set(i);
    }else for(int j:g[i]){
      if(a[u]<i||j<a[u]){
        f[i]|=f[j+1];
        f[i].set(j);
      }
    }
    for(int j=M-1;j>=0;--j){
      if(f[i][j]&&i<=a[u]&&a[u]<=j)d[u].emplace_back(i,j);
    }
  }
}
int main(){
  cin>>N;
  for(int i=0;i<N;++i)cin>>a[i],--a[i],f[i]=0;
  for(int i=0;i<N-1;++i){
    int u,v;cin>>u>>v;--u;--v;
    t[u].push_back(v);
  }
  dfs(0);
  cout<<d[0].size()<<'\n';
  return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 99 ms 1444 KB Output is correct
12 Correct 98 ms 1400 KB Output is correct
13 Correct 99 ms 1500 KB Output is correct
14 Correct 113 ms 8260 KB Output is correct
15 Correct 112 ms 8184 KB Output is correct
16 Correct 111 ms 8316 KB Output is correct
17 Correct 99 ms 1384 KB Output is correct
18 Correct 100 ms 1500 KB Output is correct
19 Correct 99 ms 3832 KB Output is correct
20 Correct 98 ms 3832 KB Output is correct