Submission #98682

#	Time	Username	Problem	Language	Result	Execution time	Memory
98682		polyfish	Uzastopni (COCI15_uzastopni)	C++14	112 / 160	858 ms	18708 KiB

uzastopni

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 10002;
const int MAX_V = 102;

int n, maxV, v[MAX_N], sz[MAX_N];
vector<int> g[MAX_N];
bitset<MAX_V> F[MAX_N][MAX_V];
bool f[2][MAX_N][MAX_V];

void readInput() {
    cin >> n;

    for (int i=1; i<=n; ++i)
        cin >> v[i];

    g[1].push_back(0);

    for (int i=1; i<n; ++i) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
}

int fixRoot(int u, int par) {
    sz[u] = 1;

    for (int i=0; i<g[u].size(); ++i) {
        int v = g[u][i];

        if (v!=par)
            sz[u] += fixRoot(v, u);
        else
            swap(g[u][0], g[u][i]);
    }

    return sz[u];
}

void dp(int u) {
    for (int i=1; i<g[u].size(); ++i)
        dp(g[u][i]);

    vector<int> p(1);
    p.push_back(u);

    for (int i=1; i<g[u].size(); ++i)
        p.push_back(g[u][i]);

    sort(p.begin(), p.end(), [](int x, int y) {
        return v[x] < v[y];
    });

    int cur = 1;
    int t = 0;

    for (int i=1; i<=maxV; ++i)
        f[t][i][0] = true;
    F[u][v[u]][1] = true;

    for (int i=0; i+1<p.size(); ++i) {
        int v = p[i+1];

        for (int l=1; l<=maxV; ++l) {
            for (int x=0; x<=min(cur, maxV-l+1); ++x) {
                for (int y=0; y<=(v!=u ? sz[v] : 1) && l+x+y-1<=maxV; ++y)
                    f[t^1][l][x+y] = false;
            }
        }

        for (int l=1; l<=maxV; ++l) {
            for (int x=0; x<=min(cur, maxV-l+1); ++x) {
                for (int y=0; y<=(v!=u ? sz[v] : 1) && l+x+y-1<=maxV; ++y)
                    f[t^1][l][x+y] |= (f[t][l][x] & F[v][l+x][y]);
            }
        }

        cur += (v!=u ? sz[v] : 1);
        t ^= 1;
    }

    for (int l=1; l<=maxV; ++l) {
        for (int x=0; x<=min(cur, maxV-l+1); ++x) {
            F[u][l][x] = F[u][l][x] || f[t][l][x];
        }
        F[u][l][0] = true;
    }
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		//freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
	fixRoot(1, 0);
    maxV = *max_element(v+1, v+n+1);
    //dp(3);
    dp(1);
    int res = 0;
    for (int i=1; i<=maxV; ++i) {
        for (int j=i; j<=maxV; ++j)
            res += F[1][i][j-i+1];
    }
    cout << res;
}

Compilation message (stderr)

uzastopni.cpp: In function 'int fixRoot(int, int)':
uzastopni.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<g[u].size(); ++i) {
                   ~^~~~~~~~~~~~
uzastopni.cpp: In function 'void dp(int)':
uzastopni.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<g[u].size(); ++i)
                   ~^~~~~~~~~~~~
uzastopni.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<g[u].size(); ++i)
                   ~^~~~~~~~~~~~
uzastopni.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i+1<p.size(); ++i) {
                   ~~~^~~~~~~~~

• Subtask 1: 112 / 160