Submission #251834

#	Time	Username	Problem	Language	Result	Execution time	Memory
251834		VEGAnn	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	380 ms	19064 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 = 10100;
const int V = 110;
const int C = 22;
const int md = 10007;
vector<int> g[N];
bitset<V> f[N][V], lf[V], clr, was[V];
int n, a[N];

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

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

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

        dfs(u, v);
    }

    clear();

    for (int i = 0; i < V; i++)
    for (int j = i; j < V; j++)
        was[i][j] = 0;

    was[a[v]][a[v]] = 1;

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

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

        for (int l = 1; l < V; l++)
        for (int r = l; r < V; r++)
            if (f[u][l][r]) {
                was[l][r] = 1;

                if (r < a[v] || l > a[v])
                    lf[l][r] = 1;
            }
    }

    for (int l = V - 1; l > 0; l--)
    for (int r = l; r < V; r++)
        if (r + 1 < V && was[l][r]) {
            if ((l == r && l == a[v])||
                (l > a[v] || r < a[v]))
                lf[l] |= lf[r + 1];
        }

    for (int l = 1; l <= a[v]; l++)
    for (int r = a[v]; r < V; r++)
        f[v][l][r] = lf[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]) {
//            cerr << l << " " << r << '\n';
            ans++;
        }

    cout << ans;

    return 0;
}

Compilation message (stderr)

uzastopni.cpp: In function 'void dfs(int, int)':
uzastopni.cpp:26:9: warning: unused variable 'lst' [-Wunused-variable]
     int lst = 0;
         ^~~

• Subtask 1: 160 / 160