Submission #1159869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159869		Der_Vlapos	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3092 ms	4680 KiB

catdog

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

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()

const int BIG = 1e9 + 10;
int x;

vector<vector<int>> tree;
vector<int> type;
int n;

vector<int> dfs(int v, int pr = -1)
{
  vector<int> cur(3);
  for (int tov : tree[v])
    if (tov != pr)
    {
      vector<int> res = dfs(tov, v);
      for (int f = 0; f < 3; ++f)
      {
        int mn = n;
        for (int tof = 0; tof < 3; ++tof)
          if (tof != f)
          {
            mn = min(mn, res[tof]);
          }
        cur[f] += min(res[f], mn + 1);
      }
    }
  if (type[v])
    cur[1 + (2 - type[v])] = cur[0] = n;
  cur[0] = min(cur[0], n);
  cur[1] = min(cur[1], n);
  cur[2] = min(cur[2], n);

  return cur;
}

int getAns()
{
  auto getCur = dfs(0);
  return min({getCur[0], getCur[1], getCur[2]});
}

void initialize(int N, std::vector<int> A, std::vector<int> B)
{
  n = N;
  tree.resize(n);
  type.resize(n, 0);
  for (int i = 0; i < n - 1; ++i)
  {
    --A[i], --B[i];
    tree[A[i]].pb(B[i]);
    tree[B[i]].pb(A[i]);
  }
}

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

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

int neighbor(int v)
{
  --v;
  type[v] = 3;
  return getAns();
}

// #include "catdog.h"
// #include <cstdio>
// #include <cassert>
// #include <vector>
// #include <stdlib.h>

// int readInt()
// {
//   int i;
//   if (scanf("%d", &i) != 1)
//   {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return i;
// }

// int main()
// {
//   int N = readInt();

//   std::vector<int> A(N - 1), B(N - 1);
//   for (int i = 0; i < N - 1; i++)
//   {
//     A[i] = readInt();
//     B[i] = readInt();
//   }
//   int Q;
//   assert(scanf("%d", &Q) == 1);
//   std::vector<int> T(Q), V(Q);
//   for (int i = 0; i < Q; i++)
//   {
//     T[i] = readInt();
//     V[i] = readInt();
//   }

//   initialize(N, A, B);

//   std::vector<int> res(Q);
//   for (int j = 0; j < Q; j++)
//   {
//     if (T[j] == 1)
//       res[j] = cat(V[j]);
//     else if (T[j] == 2)
//       res[j] = dog(V[j]);
//     else
//       res[j] = neighbor(V[j]);
//   }
//   for (int j = 0; j < Q; j++)
//     printf("%d\n", res[j]);
//   return 0;
// }

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