oj.uz

Submission #361223

# Submission time Handle Problem Language Result Execution time Memory
361223 2021-01-28T18:17:40 Z BartolM Cats or Dogs (JOI18_catdog) C++17
0 / 100
 1 ms 364 KB 
#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int MAXN=1005;

int x;
int dp[MAXN][3];
int p[MAXN];
int n;
vector <int> ls[MAXN];

int rek(int node, int fl, int par=0) {
    if (p[node] && p[node]!=fl) return INF;

    int &ret=dp[node][fl];
    if (ret!=-1) return ret;

    ret=0;
    for (int sus:ls[node]) {
        if (sus!=par) ret+=min(rek(sus, fl, node), rek(sus, 3-fl, node)+1);
    }
    return ret;
}

//prazno=0, cat=1, dog=2
void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n=N;
    for (int i=0; i<n-1; ++i) ls[A[i]].pb(B[i]), ls[B[i]].pb(A[i]);
}

int solve() {
    memset(dp, -1, sizeof dp);
    return min(rek(1, 1), rek(1, 2))+1;
}

int cat(int v) {
    p[v]=1;
    return solve();
}

int dog(int v) {
    p[v]=2;
    return solve();
}

int neighbor(int v) {
    p[v]=0;
    return solve();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -