oj.uz

Submission #894085

# Submission time Handle Problem Language Result Execution time Memory
894085 2023-12-28T00:43:07 Z box Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 6996 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 1e5;
const int INF = 1e9;

int N;
vector<int> adj[MAXN];
int must[MAXN];

ar<int, 2> dfs(int p, int i) {
    ar<int, 2> c{0, 0};
    for (int j : adj[i]) if (p != j) {
        auto v = dfs(i, j);
        c[0] += min(v[0], v[1] + 1);
        c[1] += min(v[0] + 1, v[1]);
    }
    if (must[i] & 1) c[0] = INF;
    if (must[i] & 2) c[1] = INF;
    return c;
}

int brute_dp() {
    auto v = dfs(-1, 0);
    return min(v[0], v[1]);
}

void initialize(int N, vector<int> A, vector<int> B) {
    for (int h = 0; h < N - 1; h++) {
        auto [i, j] = make_pair(A[h], B[h]);
        i--, j--;
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
}

int cat(int i) {
    i--;
    must[i] |= 1;
    return brute_dp();
}

int dog(int i) {
    i--;
    must[i] |= 2;
    return brute_dp();
}

int neighbor(int i) {
    i--;
    must[i] = 0;
    return brute_dp();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 3004 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2908 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 2908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 3004 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2908 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 2908 KB Output is correct
17 Correct 5 ms 3056 KB Output is correct
18 Correct 6 ms 3060 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 1 ms 2908 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 3008 KB Output is correct
23 Correct 9 ms 3060 KB Output is correct
24 Correct 6 ms 2908 KB Output is correct
25 Correct 3 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2972 KB Output is correct
28 Correct 2 ms 2904 KB Output is correct
29 Correct 9 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 1 ms 2908 KB Output is correct
32 Correct 2 ms 3152 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 3004 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2908 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 2908 KB Output is correct
17 Correct 5 ms 3056 KB Output is correct
18 Correct 6 ms 3060 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 1 ms 2908 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 3008 KB Output is correct
23 Correct 9 ms 3060 KB Output is correct
24 Correct 6 ms 2908 KB Output is correct
25 Correct 3 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2972 KB Output is correct
28 Correct 2 ms 2904 KB Output is correct
29 Correct 9 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 1 ms 2908 KB Output is correct
32 Correct 2 ms 3152 KB Output is correct
33 Execution timed out 3077 ms 6996 KB Time limit exceeded
34 Halted 0 ms 0 KB -