oj.uz

Submission #768701

# Submission time Handle Problem Language Result Execution time Memory
768701 2023-06-28T12:47:59 Z bgnbvnbv Uzastopni (COCI15_uzastopni) C++14
160 / 160
 197 ms 22960 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
#define bs bitset<101>
bs dp[10005][105];
ll s[maxN];
vector<ll>g[maxN];
void dfs(ll u,ll p)
{
    dp[u][s[u]][s[u]]=1;
    for(int v:g[u])
    {
        if(v!=p)
        {
            dfs(v,u);
            for(int i=1;i<=s[u];i++)
            {
                for(int j=s[u];j<=100;j++)
                {
                    dp[v][i][j]=0;
                }
            }
            for(int i=1;i<=100;i++)
            {
                dp[u][i]|=dp[v][i];
            }
        }
    }
    for(int t=1;t<=g[u].size();t++)
    {
        for(int i=1;i<=100;i++)
        {
            for(int j=i;j<=100;j++)
            {
                if(dp[u][i][j]==1)
                {
                    dp[u][i]|=dp[u][j+1];
                }
            }
        }
    }
    for(int i=1;i<s[u];i++)
    {
        for(int j=i;j<s[u];j++)
        {
            dp[u][i][j]=0;
        }
    }
    for(int i=s[u]+1;i<=100;i++)
    {
        for(int j=i;j<=100;j++)
        {
            dp[u][i][j]=0;
        }
    }
}
ll n;
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    ll ans=0;
    for(int i=1;i<=s[1];i++)
    {
        ans+=dp[1][i].count();
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

uzastopni.cpp: In function 'void dfs(ll, ll)':
uzastopni.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int t=1;t<=g[u].size();t++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5156 KB Output is correct
6 Correct 4 ms 5156 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 166 ms 21964 KB Output is correct
12 Correct 167 ms 21932 KB Output is correct
13 Correct 163 ms 21980 KB Output is correct
14 Correct 160 ms 22768 KB Output is correct
15 Correct 163 ms 22776 KB Output is correct
16 Correct 162 ms 22960 KB Output is correct
17 Correct 165 ms 22124 KB Output is correct
18 Correct 163 ms 22012 KB Output is correct
19 Correct 196 ms 21944 KB Output is correct
20 Correct 197 ms 21972 KB Output is correct