Submission #361223

#	Time	Username	Problem	Language	Result	Execution time	Memory
361223		BartolM	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	1 ms	364 KiB

catdog

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62