oj.uz

Submission #98673

# Submission time Handle Problem Language Result Execution time Memory
98673 2019-02-25T03:37:29 Z polyfish Uzastopni (COCI15_uzastopni) C++14
80 / 160
 274 ms 33792 KB 
//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];
bool F[MAX_N][MAX_V][MAX_V], f[MAX_N][MAX_V][MAX_V];         ///notice

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;

    for (int i=1; i<=maxV; ++i)
        f[0][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[i+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[i+1][l][x+y] = f[i+1][l][x+y] || (f[i][l][x] & F[v][l+x][y]);
            }
        }

        cur += (v!=u ? sz[v] : 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[p.size()-1][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

uzastopni.cpp: In function 'int fixRoot(int, int)':
uzastopni.cpp:39: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:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<g[u].size(); ++i)
                   ~^~~~~~~~~~~~
uzastopni.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<g[u].size(); ++i)
                   ~^~~~~~~~~~~~
uzastopni.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i+1<p.size(); ++i) {
                   ~~~^~~~~~~~~

Subtask #1
80.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 9 ms 1664 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 8 ms 1664 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct
10 Correct 5 ms 1664 KB Output is correct
11 Runtime error 56 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 56 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 49 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 219 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 222 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 274 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 49 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 51 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 173 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 174 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)