oj.uz

Submission #768693

# Submission time Handle Problem Language Result Execution time Memory
768693 2023-06-28T12:19:58 Z bgnbvnbv Uzastopni (COCI15_uzastopni) C++14
120 / 160
 154 ms 22832 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=2;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;
    //cout << dpl[2][1][3];
}
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=2;t<=g[u].size();t++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
120.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 5 ms 5160 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Incorrect 3 ms 5076 KB Output isn't correct
7 Incorrect 3 ms 5176 KB Output isn't correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 4 ms 5160 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct
11 Correct 129 ms 21964 KB Output is correct
12 Correct 128 ms 21892 KB Output is correct
13 Correct 130 ms 22008 KB Output is correct
14 Incorrect 125 ms 22732 KB Output isn't correct
15 Incorrect 126 ms 22832 KB Output isn't correct
16 Incorrect 124 ms 22744 KB Output isn't correct
17 Correct 139 ms 21992 KB Output is correct
18 Correct 129 ms 21952 KB Output is correct
19 Correct 154 ms 22024 KB Output is correct
20 Correct 154 ms 21992 KB Output is correct