제출 #748612

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

uzastopni

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define piii pair<int, pair<int, int>
#define v(int) vector<int>
#define si size()
#define foe(i,a,b) for(int i=a;i<=b;++i)
#define fol(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define Bit(mask,i) (1<<i)&mask
#define offBit(mask,i) (1<<i)^mask
#define onBit(mask,i) (1<<i)mask
#define CNT(x) __builtin_popcountll(x)
const ll int mod = 1e9+7;
const ll int base = 2309;
const ll int inf = 1e18;
const int N = 1e4+10;
const int LG = 20;
// ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄▄ ▄ ▄▄▄▄
// █▄▄█ █  █ █  █ █▄▄█ █  █ ██ █ █ ▄▄
// █  █ █▄▄█ █▄▄█ █  █ █▄▄█ █ ██ █▄▄█

vector<int> adj[N];
bitset<101> dp[N][105];
ll a[N], n;

bool cmp(int x, int y)
{
    return a[x] < a[y];
}
void DFS(int u, int p)
{
    foe(i,1,100)
        dp[u][i].set(i-1);
    sort(adj[u].begin(), adj[u].end(), cmp);
    bool f = 0;
    for (int v: adj[u])
    {
        if(v == p)
            continue;
        DFS(v, u);
        if (!f && a[v] >= a[u])
        {
            f = 1;
            foe(l,1,100)
            {
                int w = dp[u][l][a[u]-1];
                dp[u][l].reset();
                if(w)
                    dp[u][l].set(a[u]);
            }
        }
        foe(l,1,a[v])
            fol(r,l-1,a[v])
                if (dp[u][l][r])
                    dp[u][l] |= dp[v][r+1];
    }
    if(!f)
    {
        foe(l,1,100)
        {
            int w = dp[u][l][a[u]-1];
            dp[u][l].reset();
            if(w)
                dp[u][l].set(a[u]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    foe(i,1,n)
    {
        int x;
        cin >> x;
        dp[i][x].set(x);
        a[i] = x;
    }
    fol(i,1,n)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    DFS(1, -1);
    int ans = 0;
    foe(i,1,100)
        ans += dp[1][i].count();
    cout << ans;
}

• Subtask 1: 160 / 160