oj.uz

Submission #198129

# Submission time Handle Problem Language Result Execution time Memory
198129 2020-01-24T18:58:14 Z brcode Uzastopni (COCI15_uzastopni) C++14
160 / 160
 142 ms 19636 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5+5;
int arr[MAXN];
int n;
vector<int> v1[MAXN];
bitset<100> dp[MAXN][101];
void dfs(int curr,int par){
    for(int x:v1[curr]){
        if(x!=par){
            dfs(x,curr);
        }
    }
    for(int i=100;i>=1;i--){
        if(arr[curr] == i){
            dp[curr][i] = dp[curr][i+1];
            dp[curr][i][i] = 1;
        }
        for(int j=i;j<=100;j++){
            if(dp[curr][i][j]){
                dp[curr][i]|=dp[curr][j+1];
            }
        }
    }
    if(arr[curr]!=1){
        for(int i=100;i>=1;i--){
            if(dp[curr][i][arr[curr]-1]){
                dp[par][i]|=dp[curr][arr[curr]];
            }
        }
    }
    dp[par][arr[curr]]|=dp[curr][arr[curr]];
    int tempans = 0;
    for(int i=1;i<=5;i++){
        tempans+=dp[curr][i].count();
    }
    //cout<<tempans<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
    }
    dfs(1,100001);
    int ans = 0;
    for(int i=1;i<=100;i++){
        ans+=dp[100001][i].count();
        //cout<<dp[1][i]<<endl;
    }
    cout<<ans<<endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 121 ms 18956 KB Output is correct
12 Correct 122 ms 19028 KB Output is correct
13 Correct 122 ms 19020 KB Output is correct
14 Correct 112 ms 19576 KB Output is correct
15 Correct 114 ms 19576 KB Output is correct
16 Correct 114 ms 19636 KB Output is correct
17 Correct 123 ms 19008 KB Output is correct
18 Correct 142 ms 18944 KB Output is correct
19 Correct 116 ms 18936 KB Output is correct
20 Correct 118 ms 18936 KB Output is correct