oj.uz

Submission #679852

# Submission time Handle Problem Language Result Execution time Memory
679852 2023-01-09T12:46:31 Z vjudge1 Uzastopni (COCI15_uzastopni) C++17
160 / 160
 39 ms 20180 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 700 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Correct 1 ms 696 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 13 ms 18252 KB Output is correct
12 Correct 15 ms 18248 KB Output is correct
13 Correct 12 ms 18236 KB Output is correct
14 Correct 29 ms 20172 KB Output is correct
15 Correct 29 ms 20136 KB Output is correct
16 Correct 27 ms 20180 KB Output is correct
17 Correct 12 ms 18260 KB Output is correct
18 Correct 15 ms 18272 KB Output is correct
19 Correct 39 ms 18240 KB Output is correct
20 Correct 38 ms 18204 KB Output is correct