Submission #675314

#	Time	Username	Problem	Language	Result	Execution time	Memory
675314		vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	82 ms	24840 KiB

uzastopni

 ///
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#pragma GCC tarGet ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC tarGet("avx,avx2,fma")
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int maxN = 1e4+1;
const int N = 3e5;
const ll infty = 9e18;

void InputFile()
{
    //freopen("SHOPPING.inp","r",stdin);
    //freopen("SHOPPING.out","w",stdout);
    //freopen("test.out","r",stdin);
}

int n;
int a[10005];
vector<int> adj[10005];
bitset<105> dp[10005][105];
vector<pii> valid[10005];
vector<int> save[105];

void Read()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i < n;i++)
    {
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void DFS(int u,int p)
{
    for(int v : adj[u])
    {
        if(v == p) continue;
        DFS(v,u);
    }

    set<pii> st;
    for(int v : adj[u])
    {
        if(v == p) continue;
        for(pii x : valid[v])
        {
            st.insert(x);
        }
    }

    for(int i = 1;i <= 100;i++)
        save[i].clear();

    for(pii tmp : st)
    {
        save[tmp.fi].push_back(tmp.se);
    }

    for(int sta = 100;sta >= 1;sta--)
    {
        if(sta > a[u])
        {
            for(int p : save[sta])
            {
                dp[u][sta].set(p);
                dp[u][sta] |= dp[u][p+1];
            }
        }
        else if(sta == a[u])
        {
            dp[u][sta].set(a[u]);
            dp[u][sta] |= dp[u][sta+1];
        }
        else
        {
            for(int p : save[sta])
            {
                if(p >= a[u]) break;
                dp[u][sta].set(p);
                dp[u][sta] |= dp[u][p+1];
            }
        }
    }

    for(int sta = 1;sta <= a[u];sta++)
    {
        for(int j = a[u];j <= 100;j++)
        {
            if(dp[u][sta][j] == 1) valid[u].emplace_back(sta,j);
        }
    }
}

void Solve()
{
    DFS(1,0);
    cout << valid[1].size();
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //InputFile();
    //int subtask;
    //cin >> subtask;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

uzastopni.cpp:7: warning: ignoring '#pragma GCC tarGet' [-Wunknown-pragmas]
    7 | #pragma GCC tarGet ("avx2")
      | 
uzastopni.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
uzastopni.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
uzastopni.cpp:11: warning: ignoring '#pragma GCC tarGet' [-Wunknown-pragmas]
   11 | #pragma GCC tarGet("avx,avx2,fma")
      |

• Subtask 1: 160 / 160