oj.uz

Submission #251709

# Submission time Handle Problem Language Result Execution time Memory
251709 2020-07-22T08:35:51 Z VEGAnn Uzastopni (COCI15_uzastopni) C++14
0 / 160
 275 ms 65540 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<N> f[N][V], lf[2][V], rt[2][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){
//    f[v][a[v]][a[v]] = 1;

    cerr << v << '\n';

    clear(0);

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

    int lst = 0;

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

        dfs(u, v);

        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][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]);
            }

        for (int l = 1; l < V; l++)
        for (int r = l; r < V; r++){
            bool res = bool(lf[lst][l][r] || rt[lst][r][l] || lf[lst ^ 1][l][r] || rt[lst ^ 1][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++)
        f[v][l][r] = lf[lst][l][r];
}

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])
            ans++;

    cout << ans;

    return 0;
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7296 KB Output isn't correct
2 Incorrect 11 ms 9728 KB Output isn't correct
3 Incorrect 13 ms 11008 KB Output isn't correct
4 Incorrect 13 ms 11008 KB Output isn't correct
5 Incorrect 16 ms 13568 KB Output isn't correct
6 Incorrect 16 ms 13568 KB Output isn't correct
7 Incorrect 15 ms 13568 KB Output isn't correct
8 Incorrect 16 ms 13560 KB Output isn't correct
9 Incorrect 16 ms 13528 KB Output isn't correct
10 Incorrect 16 ms 13568 KB Output isn't correct
11 Runtime error 94 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 87 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 88 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 262 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 275 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 260 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 92 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 88 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 88 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 88 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)