답안 #251751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251751 2020-07-22T09:16:37 Z VEGAnn Uzastopni (COCI15_uzastopni) C++14
56 / 160
500 ms 18876 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Incorrect 5 ms 768 KB Output isn't correct
4 Incorrect 5 ms 768 KB Output isn't correct
5 Incorrect 7 ms 768 KB Output isn't correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 7 ms 768 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 8 ms 768 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Execution timed out 610 ms 16892 KB Time limit exceeded
12 Execution timed out 592 ms 16760 KB Time limit exceeded
13 Execution timed out 584 ms 16832 KB Time limit exceeded
14 Execution timed out 632 ms 18876 KB Time limit exceeded
15 Execution timed out 626 ms 18808 KB Time limit exceeded
16 Execution timed out 623 ms 18680 KB Time limit exceeded
17 Execution timed out 599 ms 16760 KB Time limit exceeded
18 Execution timed out 589 ms 16884 KB Time limit exceeded
19 Execution timed out 597 ms 16760 KB Time limit exceeded
20 Execution timed out 607 ms 16888 KB Time limit exceeded