Submission #768701

#	Time	Username	Problem	Language	Result	Execution time	Memory
768701		bgnbvnbv	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	197 ms	22960 KiB

uzastopni

#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 (stderr)

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 / 160