# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1151333 | AgentPengin | Cats or Dogs (JOI18_catdog) | C++20 | 0 ms | 0 KiB |
/**
* author: AgentPengin ( Độc cô cầu bại )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include<bits/stdc++.h>
#define "catdog.h"
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;
int n,dp[MAXN][3],c[MAXN];
vector<int> adj[MAXN];
void initialize(int _n,vector<int> a, vector<int> b) {
n = _n;
for (int i = 0;i < n - 1;i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
}
void dfs(int u,int p) {
dp[u][1] = dp[u][2] = 0;
for (auto v : adj[u]) {
if (v != p) {
dfs(v, u);
dp[u][1] += min(dp[v][1], dp[v][2] + 1);
dp[u][2] += min(dp[u][2], dp[v][1] + 1);
}
}
if (c[u] == 1) dp[u][2] = 1e9;
else dp[u][1] = 1e9;
}
int cat(int v) {
c[v] = 1;
dfs(1, 1);
return min(dp[1][1],dp[1][2]);
}
int dog(int v) {
c[v] = 2;
dfs(1, 1);
return min(dp[1][1],dp[1][2]);
}
int neighbor(int v) {
c[v] = 0;
dfs(1, 1);
return min(dp[1][1],dp[1][2]);
}