이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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]);
}
컴파일 시 표준 에러 (stderr) 메시지
catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < a[u].size(); i++){
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |