Submission #496539

#	Time	Username	Problem	Language	Result	Execution time	Memory
496539		600Mihnea	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3039 ms	6220 KiB

catdog

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

using namespace std;


const int N = (int) 1e5 + 7;
const int INF = (int) 1e9 + 7;
int n;
int kitty[N];
int doge[N];
int cost_kitty[N];
int cost_doge[N];
vector<int> g[N];

void build(int a, int p = -1) {
  vector<int> kids;
  for (auto &b : g[a]) {
    if (b != p) {
      kids.push_back(b);
      build(b, a);
    }
  }
  g[a] = kids;
}

void dfs(int a) {
  kitty[a] = cost_kitty[a];
  doge[a] = cost_doge[a];
  for (auto &b : g[a]) {
    dfs(b);
    kitty[a] += min(kitty[b], 1 + doge[b]);
    doge[a] += min(doge[b], 1 + kitty[b]);
  }
}

void initialize(int nn, std::vector<int> edgesA, std::vector<int> edgesB) {
  n = nn;
  for (int i = 0; i < n - 1; i++) {
    int a = edgesA[i];
    int b = edgesB[i];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  build(1);

}

int cat(int v) {
  cost_kitty[v] = INF;
  cost_doge[v] = 0;
  dfs(1);
  return min(kitty[1], doge[1]);
}

int dog(int v) {
  cost_kitty[v] = 0;
  cost_doge[v] = INF;
  dfs(1);
  return min(kitty[1], doge[1]);
}

int neighbor(int v) {
  cost_kitty[v] = 0;
  cost_doge[v] = 0;
  dfs(1);
  return min(kitty[1], doge[1]);
}

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