Submission #679852

#	Time	Username	Problem	Language	Result	Execution time	Memory
679852		vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	39 ms	20180 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int maxk = 110;
bitset<maxk> dp[maxn][maxk],none;
int a[maxn];
vector <int> adj[maxn];
int n,k;
bool cmp(int x, int y)
{
    return a[x]<a[y];
}
void dfs(int x, int p)
{
    vector <int> tmp;
    for (int i:adj[x])
        if (i!=p)
            dfs(i,x), tmp.push_back(i);
    for (int i=1; i<=k; i++) dp[x][i].set(i-1,1);
    sort(tmp.begin(),tmp.end(),cmp);
    int l,r;
    bool check=0;
    for (int i=0; i<tmp.size(); i++)
    {
        if (i==0||tmp[i]!=tmp[i-1]) l=i;
        if (i==tmp.size()-1||tmp[i]!=tmp[i+1])
        {
            r=i;
            if (!check&&a[tmp[i]]>=a[x])
            {
                check=1;
                for (int ll=1; ll<=k; ll++)
                {
                    int val = dp[x][ll][a[x]-1];
                    dp[x][ll]&=none;
                    if(val) dp[x][ll].set(a[x],1);
                }
            }
            for (int j=l; j<=r; j++){
                for (int ll=1; ll<=a[tmp[j]]; ll++)
                    for (int z=ll-1; z<a[tmp[j]]; z++)
                        if (dp[x][ll][z]) dp[x][ll]|=(dp[tmp[j]][z+1]);
//            if (x==1){
//    cout<<x<<" : "<<tmp[j]<<" ------------------\n";
//    for (int ll=1; ll<=k; ll++)
//        for (int rr=1; rr<=k; rr++)
//            cout<<ll<<' '<<rr<<": "<<dp[x][ll][rr]<<'\n';
            }
        }
    }
    if (!check)
    {
        check=1;
        for (int ll=1; ll<=k; ll++)
        {
            int val = dp[x][ll][a[x]-1];
            dp[x][ll]&=none;
            if(val) dp[x][ll].set(a[x],1);
        }
    }
//    cout<<x<<" !!!!!!!\n";
//    for (int ll=1; ll<=k; ll++)
//        for (int rr=1; rr<=k; rr++)
//            cout<<ll<<' '<<rr<<": "<<dp[x][ll][rr]<<'\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    k=0;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
        k=max(k,a[i]);
    }
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    int ans=0;
    for (int i=1; i<=k; i++) ans+=dp[1][i].count();
    cout<<ans;
}

Compilation message (stderr)

uzastopni.cpp: In function 'void dfs(int, int)':
uzastopni.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i=0; i<tmp.size(); i++)
      |                   ~^~~~~~~~~~~
uzastopni.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (i==tmp.size()-1||tmp[i]!=tmp[i+1])
      |             ~^~~~~~~~~~~~~~

• Subtask 1: 160 / 160