| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 72623 | ekrem | Cats or Dogs (JOI18_catdog) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "catdog.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 1000005
using namespace std;
typedef vector < int > vi;
int a[N], dp[2][N];
vi gg[N], g[N];
int f(int node, int dur){
int &r = dp[dur][node];
if(r != -1)
return r;
r = 0;
if(a[node] and a[node] - 1 != dur)
return r = inf;
for(int i = 0; i < g[node].size(); i++){
int coc = g[node][i];
r += min(f(coc, dur), f(coc, !dur) + 1);
}
// if(a[1] == 2)
// cout << node << " " << dur << " -> " << r << endl;
return r;
}
void hazirla(int node, int par){
for(int i = 0; i < gg[node].size(); i++)
if(gg[node][i] != par){
g[node].pb(gg[node][i]);
hazirla(gg[node][i], node);
}
}
void initialize(int n, vi a, vi b){
for(int i = 0; i < n - 1; i++){
gg[a[i]].pb(b[i]);
gg[b[i]].pb(a[i]);
}
hazirla(1, -1);
}
int cat(int v){
memset(dp, -1, sizeof dp);
a[v] = 1;
return min(f(1, 0), f(1, 1));
}
int dog(int v){
memset(dp, -1, sizeof dp);
a[v] = 2;
return min(f(1, 0), f(1, 1));
}
int neighbor(int v){
memset(dp, -1, sizeof dp);
a[v] = 0;
return min(f(1, 0), f(1, 1));
}
int main(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int n, q;
scanf("%d",&n);
vi a(n - 1), b(n - 1);
for(int i = 0; i < n - 1; i++)
scanf("%d %d",&a[i] ,&b[i]);
scanf("%d",&q);
vi t(q), v(q);
for(int i = 0; i < q; i++)
scanf("%d %d",&t[i] ,&v[i]);
initialize(n, a, b);
vi ans(q);
for(int i = 0; i < q; i++){
if(t[i] == 1)
ans[i] = cat(v[i]);
else if(t[i] == 2)
ans[i] = dog(v[i]);
else
ans[i] = neighbor(v[i]);
}
for(int i = 0; i < q; i++)
printf("%d\n",ans[i]);
return 0;
}