oj.uz

Submission #366691

# Submission time Handle Problem Language Result Execution time Memory
366691 2021-02-15T03:10:17 Z Mamnoon_Siam Cats or Dogs (JOI18_catdog) C++17
0 / 100
 2 ms 2668 KB 
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 1e5 + 5;
const int inf = 1e9 + 5;

int n;
int state[N];
int dp[N][3];
vi g[N];

void chkmin(int& x, int y) {
  x = min(x, y);
}

void solve(int u, int dad = 0) {
  for(int v : g[u]) if(v != dad) {
    solve(v, u);
  }
  dp[u][0] = dp[u][1] = dp[u][2] = inf;
  dp[u][state[u]] = 0;
  for(int v : g[u]) if(v != dad) {
    vi me(dp[u], dp[u]+3), ch(dp[v], dp[v]+3);
    dp[u][0] = dp[u][1] = dp[u][2] = inf;
    for(int i : {0,1,2}) {
      for(int j : {0,1,2}) {
        chkmin(dp[u][i], me[i] + ch[j] + 1);
        if((i|j) != 3) {
          chkmin(dp[u][i|j], me[i] + ch[j]);
        }
      }
    }
  }
}

void initialize(int _n, std::vector<int> A, std::vector<int> B) {
  n = _n;
  for(int i = 0; i < sz(A); ++i) {
    g[A[i]].emplace_back(B[i]);
    g[B[i]].emplace_back(A[i]);
  }
}

int cat(int v) {
  state[v] = 1;
  solve(1);
  return *min_element(dp[1], dp[1]+4);
}

int dog(int v) {
  state[v] = 2;
  solve(1);
  return *min_element(dp[1], dp[1]+4);
}

int neighbor(int v) {
  state[v] = 0;
  solve(1);
  return *min_element(dp[1], dp[1]+4);
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 62.0

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