Submission #675288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
675288	2022-12-27T03:50:07 Z	vjudge1	Uzastopni (COCI15_uzastopni)	C++17	80 / 160	126 ms	49324 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[maxN];
vector<int> adj[maxN];
vector<int> save[101];
bitset<101> dp[maxN][101];
vector<pii> valid[1001];

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

80.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	724 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Runtime error	15 ms	7324 KB	Execution killed with signal 6
12	Runtime error	12 ms	7124 KB	Execution killed with signal 11
13	Runtime error	20 ms	8404 KB	Execution killed with signal 6
14	Incorrect	100 ms	24588 KB	Output isn't correct
15	Incorrect	92 ms	24476 KB	Output isn't correct
16	Runtime error	126 ms	49324 KB	Execution killed with signal 6
17	Runtime error	13 ms	9044 KB	Execution killed with signal 11
18	Runtime error	12 ms	7508 KB	Execution killed with signal 11
19	Runtime error	9 ms	5460 KB	Execution killed with signal 11
20	Runtime error	10 ms	3540 KB	Execution killed with signal 11