Submission #363236

#	Time	Username	Problem	Language	Result	Execution time	Memory
363236		buyolitsez	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	49 ms	4408 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

int x;

const int MAXN = 1000 + 15;
const int INF = 2139062143;

vector <int> adj[MAXN];
int type[MAXN];
int dp[MAXN][3];
int mn[MAXN];

void initialize(int N, std::vector<int> A, std::vector<int> B) {
  x = A.size();
  memset(type, 0, sizeof(type));
  for (int i = 0; i < x; ++i) {
  	int a = A[i], b = B[i];
  	adj[a].emplace_back(b);
  	adj[b].emplace_back(a);
  }
}

void DFS(int v, int p = -1) {
	for (auto u : adj[v]) {
		if (u != p) {
            DFS(u, v);
        }
	}
	for (int myType = 0; myType < 3; ++myType) {
        if (type[v] != 0 && myType != type[v]) {continue;}
        dp[v][myType] = 0;
        for (auto u : adj[v]) {
            if (u == p) {continue;}
            //удаляю ребро
            int now = mn[u] + 1;
            for (int nxtType = 0; nxtType < 3; ++nxtType) {
                if (dp[u][nxtType] == INF) { continue; }
                // оставляю ребро
                if (nxtType != 0 && myType != nxtType) { continue; }
                now = min(now, dp[u][nxtType]);
            }
            dp[v][myType] += now;
        }
    }
	mn[v] = min({dp[v][0], dp[v][1], dp[v][2]});
}

int Calc() {
	memset(dp, 127, sizeof(dp));
	memset(mn, 127, sizeof(mn));
	DFS(1);
	return mn[1];
}

int cat(int v) {
	type[v] = 1;
	return Calc();
}

int dog(int v) {
	type[v] = 2;
	return Calc();
}

int neighbor(int v) {
	type[v] = 0;
	return Calc();
}

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 0 / 62