| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1285417 | trandangquang | Cats or Dogs (JOI18_catdog) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=1010;
int n,dp[N][2],cd[N];
vector<int>adj[N];
void initalize(int _n, int _a[], int _b[]){
n=_n;
rep(i,n-1){
adj[_a[i]].eb(_b[i]);
adj[_b[i]].eb(_a[i]);
}
memset(cd,-1,sizeof(cd));
}
void dfs(int u, int p=-1){
for(int v:adj[u]) if(v!=p){
dfs(v,u);
}
if(cd[u]==-1){
dp[u][0]=dp[u][1]=0;
for(int v:adj[u]) if(v!=p){
dp[u][0]+=min(dp[v][0],dp[u][1]+1);
dp[u][1]+=min(dp[v][1],dp[u][0]+1);
}
} else{
dp[u][cd[u]]=0; dp[u][cd[u]^1]=1e9;
for(int v:adj[u]) if(v!=p){
dp[u][cd[u]]+=min(dp[v][cd[u]],dp[v][cd[u]^1]+1);
}
}
}
void cat(int x){
cd[x]=0;
dfs(0);
return min(dp[0][1],dp[0][0]);
}
void dog(int x){
cd[x]=1;
dfs(0);
return min(dp[0][1],dp[0][0]);
}
void neighbor(int x){
cd[x]=-1;
dfs(0);
return min(dp[0][1],dp[0][0]);
}
//
//int32_t main(){
// #define task "test"
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// cin.tie(0)->sync_with_stdio(0);
//
// int tc=1; //cin>>tc;
// rep(i,tc){
// solve();
// }
//}
