| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1119418 | kiethm07 | Cats or Dogs (JOI18_catdog) | C++11 | 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>
#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define TEXT "CatsorDogs"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;
int n;
vector<int> a[N];
int f[N], g[N];
int preF[N], preG[N];
int type[N];
int pa[N];
void dfs(int u,int p){
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i];
if (v == p) continue;
pa[v] = u;
dfs(v,u);
}
}
void brute(int u,int p){
if (type[u] == 0) f[u] = g[u] = 0;
if (type[u] == 1) f[u] = 0, g[u] = inf;
if (type[u] == 2) f[u] = inf, g[u] = 0;
for(int v : a[u]){
if (v == p) continue;
brute(v,u);
if (f[u] != inf) f[u] += min(f[v], g[v] + 1);
if (g[u] != inf) g[u] += min(f[v] + 1, g[v]);
}
}
void initialize(int N,vector<int> u, vector<int> v){
n = N;
for (int i = 0; i < n - 1; i++){
a[u[i]].push_back(v[i]);
a[v[i]].push_back(u[i]);
}
dfs(1,-1);
}
int cat(int u){
type[u] = 1;
// brute(1,-1);
g[u] = inf;
while(u != 0){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
else f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
else g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
return min(f[1], g[1]);
}
int dog(int u){
type[u] = 2;
f[u] = inf;
while(u != 0){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
else f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
else g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
// brute(1,-1);
return min(f[1], g[1]);
}
int neighbor(int u){
type[u] = 0;
f[u] = g[u] = 0;
for (int v : a[u]){
if (v == pa[u]) continue;
f[u] += min(f[v], g[v] + 1);
g[u] += min(g[v], f[v] + 1);
}
while(u != 0){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
else f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
else g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
// brute(1,-1);
return min(f[1], g[1]);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
if (fopen(TEXT".inp","r")){
freopen(TEXT".inp","r",stdin);
freopen(TEXT".out","w",stdout);
}
// int N = 5;
// vector<int> A = {1,2,2,4};
// vector<int> B = {2,3,4,5};
// initialize(N,A,B);
// vector<pii> order = {pii(1,3),pii(2,5),pii(1,2),pii(2,1),pii(3,2)};
// for (auto [type, u] : order){
// if (type == 1) cout << cat(u) << "\n";
// if (type == 2) cout << dog(u) << "\n";
// if (type == 3) cout << neighbor(u) << "\n";
// }
int N;
cin >> N;
vi A(N - 1), B(N - 1);
for (int i = 0; i < N - 1; i++){
cin >> A[i] >> B[i];
}
initialize(N,A,B);
int Q;
cin >> Q;
for (int i = 0; i < Q; i++){
int type,u;
cin >> type >> u;
if (type == 1) cout << cat(u) << "\n";
if (type == 2) cout << dog(u) << "\n";
if (type == 3) cout << neighbor(u) << "\n";
}
return 0;
}