Submission #675314

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
675314	2022-12-27T03:56:10 Z	vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	82 ms	24840 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	852 KB	Output is correct
2	Correct	1 ms	852 KB	Output is correct
3	Correct	1 ms	852 KB	Output is correct
4	Correct	1 ms	852 KB	Output is correct
5	Correct	1 ms	852 KB	Output is correct
6	Correct	2 ms	980 KB	Output is correct
7	Correct	1 ms	980 KB	Output is correct
8	Correct	1 ms	980 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	1 ms	852 KB	Output is correct
11	Correct	25 ms	17868 KB	Output is correct
12	Correct	26 ms	17916 KB	Output is correct
13	Correct	20 ms	17816 KB	Output is correct
14	Correct	82 ms	24840 KB	Output is correct
15	Correct	80 ms	24840 KB	Output is correct
16	Correct	80 ms	24716 KB	Output is correct
17	Correct	26 ms	17876 KB	Output is correct
18	Correct	25 ms	17804 KB	Output is correct
19	Correct	62 ms	20444 KB	Output is correct
20	Correct	63 ms	20460 KB	Output is correct