Submission #546490

#	Time	Username	Problem	Language	Result	Execution time	Memory
546490		RaresFelix	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	2 ms	2900 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define MN 107171
#define INF int(1e7)
#pragma GCC optimize("unroll-loops")

using namespace std;

int x;

struct cost {int V[2][2]; } V[4 * MN];
namespace AINT {
    int len;
    cost nil;
    cost uni(const cost &a, const cost &b) {
        cost r;
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                r.V[i][j] = INF;
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                for(int k = 0; k < 2; ++k)
                    for(int f = 0; f < 2; ++f)
                        r.V[i][f] = min(r.V[i][f], a.V[i][j] + b.V[k][f] + (j != k));
        return r;
    }
    void update(int p, cost v, int u = 1, int s = 1, int d = len) {
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
            return;
        }
        update(p, v, u * 2, s, (s + d) >> 1);
        update(p, v, u * 2 + 1, (s + d) / 2 + 1, d);
        V[u] = uni(V[u * 2], V[u * 2 + 1]);
        V[u] = V[u];
    }
    cost query_i(int l, int r, int u = 1, int s = 1, int d = len) {
        if(r < s || d < l) return nil;
        if(l <= s && d <= r) return V[u];
        return uni(query_i(l, r, u * 2, s, (s + d) / 2),
                   query_i(l, r, u * 2 + 1, (s + d) / 2 + 1, d));
    }
}
/// 0 - cat 1 - dog
vector<int> L[MN];
int heavySon[MN], sz[MN], Par[MN], Nod[MN];
void dfs1(int u, int p) {
    sz[u] = 1;
    Par[u] = p;
    int fiu_h = -1, s_fiu = -1;
    for(auto it : L[u])
        if(it != p) {
            dfs1(it, u), sz[u] += sz[it];
            if(sz[it] > s_fiu) {
                s_fiu = sz[it];
                fiu_h = it;
            }
        }
    heavySon[u] = fiu_h;
}
int Dp0[MN], Dp1[MN]; // pt nodurile rascruce, dp-ul pt fiecare componenta
///Dp0 si Dp1 sunt influentele exterioare asupra unui element, nu costul real!

//asign id's
int StartComp[MN], EndComp[MN], NodePoz[MN], ParComp[MN], COUNTER_GLOBAL, COMP_GLOB, Comp[MN];
///la Start e pusa radacina lantului, la End ultimul nod!

void dfs2(int u, int p, int cul) {
    NodePoz[u] = ++COUNTER_GLOBAL;
    Nod[COUNTER_GLOBAL] = u;
    if(!StartComp[cul]) StartComp[cul] = NodePoz[u];
    EndComp[cul] = max(EndComp[cul], NodePoz[u]);
    Comp[u] = cul;
    if(sz[u] != 1)
        dfs2(heavySon[u], u, cul);
    for(auto it : L[u])
        if(it != p && it != heavySon[u]) {
            ParComp[++COMP_GLOB] = cul;
            dfs2(it, u, COMP_GLOB);
        }
}



void initialize(int N, std::vector<int> A, std::vector<int> B) {
    for(int i = 0; i < N - 1; ++i)
        L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
    dfs1(1, 0);
    dfs2(1, 0, ++COMP_GLOB);
    AINT::len = COUNTER_GLOBAL;
}
int Cul[MN];
int RealDP0[MN], RealDP1[MN];
cost calcnod(int u) {
    cost nou;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            nou.V[i][j] = INF;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j){
            nou.V[i][j] = min(nou.V[i][j], (Cul[u] == 1 ? INF : Dp0[u]) + i + j);
            nou.V[i][j] = min(nou.V[i][j], (Cul[u] == 0 ? INF : Dp1[u]) + !i + !j);
        }
    return nou;
}
void update(int u, int val) {
    Cul[u] = val;
    AINT::update(NodePoz[u], calcnod(u));
    int cur_comp = Comp[u];
    while(cur_comp) {
        //valoare parinte
        cost val = AINT::query_i(StartComp[cur_comp], EndComp[cur_comp]);
        u = Nod[StartComp[cur_comp]];
        int last0 = RealDP0[u], last1 = RealDP1[u];
        RealDP0[u] = min(val.V[0][0], val.V[0][1]);
        RealDP1[u] = min(val.V[1][0], val.V[1][1]);
        int delta0par = 0, delta1par = 0;
        delta0par = min(RealDP1[u] + 1, RealDP0[u]) - min(last1 + 1, last0);
        delta1par = min(RealDP0[u] + 1, RealDP1[u]) - min(last0 + 1, last1);
        int parc = ParComp[cur_comp], par = Par[u];
        Dp0[par] += delta0par;
        Dp1[par] += delta1par;
        AINT::update(NodePoz[par], calcnod(par));
        cur_comp = parc;
        u = par;
    }
}

int cat(int v) {
    update(v, 0);
    return min(Dp0[0], Dp1[0]);
}

int dog(int v) {
    update(v, 1);
    return min(Dp0[0], Dp1[0]);
}

int neighbor(int v) {
    update(v, -1);
    return min(Dp0[0], Dp1[0]);
}

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