oj.uz

Submission #91875

# Submission time Handle Problem Language Result Execution time Memory
91875 2018-12-30T20:29:07 Z sjhuang26 Uzastopni (COCI15_uzastopni) C++14
80 / 160
 135 ms 8292 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]){
      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
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Incorrect 3 ms 760 KB Output isn't correct
4 Incorrect 3 ms 740 KB Output isn't correct
5 Incorrect 3 ms 760 KB Output isn't correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 892 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Incorrect 132 ms 1276 KB Output isn't correct
12 Incorrect 105 ms 1384 KB Output isn't correct
13 Correct 104 ms 1272 KB Output is correct
14 Incorrect 121 ms 8148 KB Output isn't correct
15 Incorrect 135 ms 8292 KB Output isn't correct
16 Incorrect 120 ms 8184 KB Output isn't correct
17 Correct 109 ms 1272 KB Output is correct
18 Correct 108 ms 1360 KB Output is correct
19 Incorrect 110 ms 3704 KB Output isn't correct
20 Incorrect 111 ms 3612 KB Output isn't correct