제출 #675328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675328		vjudge1	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	78 ms	24388 KiB

uzastopni

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int, int>

using namespace std;

const int mxN = 1e4 + 5;
const int BIT = 1e2 + 5;

int numNode, a[mxN];
vector <int> adj[mxN], q[BIT];
vector <pii> s[mxN];
bitset <BIT> bit[mxN][BIT];

void Shiba_Read()
{
    cin >> numNode;
    for (int i = 1; i <= numNode; ++i)
        cin >> a[i];
    for (int i = 2; i <= numNode; ++i)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

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

    for (int i = 0; i < BIT; ++i) q[i].clear();

    for (int v : adj[u])
    {
        if (v != p)
        {
            for (pii it : s[v])
                q[it.fi].push_back(it.se);
        }
    }

    for (int i = BIT - 1; i >= 1; --i)
    {
        if (i == a[u])
        {
            bit[u][i] |= bit[u][i + 1];
            bit[u][i].set(i);
        }
        else
        {
            for (int j : q[i])
            {
                if (i > a[u] || j < a[u])
                {
                    bit[u][i] |= bit[u][j + 1];
                    bit[u][i].set(j);
                }
            }
        }

        for (int j = BIT - 1; j >= i; --j)
        {
            if (bit[u][i].test(j) && a[u] >= i && a[u] <= j)
                s[u].push_back(make_pair(i, j));
        }
    }
}

void Shiba_Process()
{
    Shiba_Dfs(1, 0);
    cout << s[1].size();
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Shiba_Read();
    Shiba_Process();
    return 0;
}

• Subtask 1: 160 / 160