Submission #1119388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119388		kiethm07	Cats or Dogs (JOI18_catdog)	C++11	0 / 100	3 ms	2640 KiB

catdog

#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 "a"

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 != 1){
        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);
            if (preG[u] + 1 <= preF[u]) 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]);
            if (preF[u] + 1 <= preG[u]) 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 != 1){
        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);
            if (preG[u] + 1 <= preF[u]) 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]);
            if (preF[u] + 1 <= preG[u]) 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 != 1){
        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);
            if (preG[u] + 1 <= preF[u]) 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]);
            if (preF[u] + 1 <= preG[u]) 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";
//    }
//    return 0;
//}

Compilation message (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++){
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62