Submission #675304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
675304	2022-12-27T03:53:45 Z	vjudge1	Uzastopni (COCI15_uzastopni)	C++17	136 / 160	130 ms	46624 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[10001];
vector<int> adj[10001];
bitset<101> dp[10001][101];
vector<pii> valid[10001];

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);
        }
    }

    vector<int> save[101];

    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

136.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	2 ms	852 KB	Output is correct
4	Correct	1 ms	852 KB	Output is correct
5	Correct	1 ms	980 KB	Output is correct
6	Correct	2 ms	1108 KB	Output is correct
7	Correct	2 ms	1108 KB	Output is correct
8	Correct	1 ms	1108 KB	Output is correct
9	Correct	1 ms	980 KB	Output is correct
10	Correct	1 ms	980 KB	Output is correct
11	Correct	29 ms	17264 KB	Output is correct
12	Correct	34 ms	17248 KB	Output is correct
13	Correct	32 ms	17236 KB	Output is correct
14	Runtime error	109 ms	46624 KB	Memory limit exceeded
15	Runtime error	130 ms	46612 KB	Memory limit exceeded
16	Runtime error	115 ms	46620 KB	Memory limit exceeded
17	Correct	30 ms	17308 KB	Output is correct
18	Correct	30 ms	17268 KB	Output is correct
19	Correct	82 ms	19760 KB	Output is correct
20	Correct	80 ms	19840 KB	Output is correct