Submission #251751

#	Time	Username	Problem	Language	Result	Execution time	Memory
251751		VEGAnn	Uzastopni (COCI15_uzastopni)	C++14	56 / 160	632 ms	18876 KiB

uzastopni

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 10010;
const int V = 101;
const int C = 22;
const int md = 10007;
vector<int> g[N];
bitset<V> f[N][V], lf[3][V], rt[3][V], clr;
int n, a[N];

void clear(int tp){
    for (int i = 0; i < V; i++){
        lf[tp][i] = clr;
        rt[tp][i] = clr;
    }
}

void dfs(int v, int p){
    int lst = 0;

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);
    }

    clear(0);

    lf[0][a[v]][a[v]] = 1;
    rt[0][a[v]][a[v]] = 1;

    for (int u : g[v]){
        if (u == p) continue;

//        cerr << lf[lst][1][3] << '\n';

        lst ^= 1;

        clear(lst);

        for (int l = 1; l < V; l++)
        for (int r = l; r < V; r++)
            if (f[u][l][r] && !lf[lst ^ 1][l][r]){
                lf[lst][l][r] = 1;

                if (r + 1 < V)
                    lf[lst][l] |= (lf[lst ^ 1][r + 1]);

                rt[lst][r][l] = 1;

                if (l > 1)
                    rt[lst][r] |= (rt[lst ^ 1][l - 1]);
            }

        clear(2);

        for (int r = 2; r < V; r++)
        for (int l = r - 1; l > 0; l--) {
            if (rt[lst][r - 1][l] || lf[lst][l][r - 1])
                lf[2][l] |= lf[lst ^ 1][r];

            if (lf[lst ^ 1][l][r])
                lf[2][l] |= lf[lst][r];
            //right too
        }

        for (int l = 2; l < V; l++)
        for (int r = l; r < V; r++){
            if (rt[lst][r][l] || lf[lst][l][r])
                rt[2][r] |= rt[lst ^ 1][l - 1];

            if (rt[lst ^ 1][l][r])
                rt[2][r] |= rt[lst][l - 1];
        }

        for (int l = 1; l < V; l++)
        for (int r = l; r < V; r++){
            bool res = bool(lf[2][l][r] || rt[2][r][l] || lf[lst ^ 1][l][r] || rt[lst ^ 1][r][l] || lf[lst][l][r] || rt[lst][r][l]);

            lf[lst][l][r] = res;
            rt[lst][r][l] = res;
        }
    }

    for (int l = 1; l < V; l++)
    for (int r = l; r < V; r++)
        if (l <= a[v] && r >= a[v])
            f[v][l][r] = lf[lst][l][r];

//    if (v == 1) {
//        cerr << "ADSGDA " << f[v][1][3] << '\n';
//        cerr << "ADSGDA " << f[v][2][3] << '\n';
//        cerr << "ADSGDA " << f[v][3][3] << '\n';
//    }
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    dfs(0, -1);

    int ans = 0;

    for (int l = 1; l < V; l++)
    for (int r = l; r < V; r++)
        if (f[0][l][r]) {
//            cerr << l << " " << r << '\n';
            ans++;
        }

    cout << ans;

    return 0;
}

• Subtask 1: 56 / 160