Submission #558849

#	Time	Username	Problem	Language	Result	Execution time	Memory
558849		RaresFelix	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	639 ms	25952 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define MN 100071

using namespace std;

int n, Sz[MN];
vector<int> L[MN];

const int kInf = numeric_limits<int>::max() / 4;
struct mat {
    int v[2][2];
    mat() {
        v[0][0] = v[1][1] = 0;
        v[0][1] = v[1][0] = kInf;
    }
    mat(int a, int b, int c, int d) {
        v[0][0] = a, v[0][1] = b, v[1][0] = c, v[1][1] = d;
    }
} I;
void afis(mat a);
namespace AINT {
    mat uni(const mat &a, const mat &b) {
        mat re(kInf, kInf, kInf, kInf);
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j) 
                for(int k = 0; k < 2; ++k)
                    for(int w = 0; w < 2; ++w)
                        re.v[i][w] = min(re.v[i][w], a.v[i][j] + b.v[k][w] + (j ^ k));
        return re;
    }
    mat V[4 * MN];
    int len;
    void init() {
        //for(int i = 0; i < 4 * MN; ++i) V[i] = r0;
    }
    void update(int p, mat v, int u = 1, int s = 1, int d = len) {
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
        //printf("Starea nodului %d(%d, %d) din AINT:\n", u, s, d);
        afis(V[u]);
        //printf("||||||||||||||\n");
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = uni(V[u << 1], V[u << 1 | 1]);
        //printf("Starea nodului %d(%d, %d) din AINT:\n", u, s, d);
        afis(V[u]);
        //printf("||||||||||||||\n");
    }
    mat query(int l, int r, int u = 1, int s = 1, int d = len) {
        if(r < s || d < l) return I;
        if(l <= s && d <= r) {
            return V[u];
        }
        int mij = (s + d) >> 1;
        if(r <= mij) return query(l, r, u << 1, s, (s + d) >> 1);
        if(mij < l) return query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        return uni(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
    }
}
int Par[MN], In[MN], Out[MN], tmr, Nxt[MN];
int CFD[MN][2]; //cost fii secundari

int TipHut[MN];

void recalc_mat(int u) {
    mat re;
    if(TipHut[u] == 0) {
        re.v[0][0] = 0;
        re.v[1][1] = kInf;
    }
    if(TipHut[u] == 1) {
        re.v[0][0] = kInf;
        re.v[1][1] = 0;
    }
    if(TipHut[u] == 2) {
        re.v[0][0] = 0;
        re.v[1][1] = 0;
    }
    re.v[0][1] = kInf;
    re.v[1][0] = kInf;
    re.v[0][0] += CFD[u][0];
    re.v[1][1] += CFD[u][1];
    //printf("    !!! Pt nodul %d am recalc matricea:\n", u);
    afis(re);
    //printf("\n\n");
    AINT::update(In[u], re);
}
void afis(mat a) {
    //printf("%d %d\n%d %d\n", a.v[0][0], a.v[0][1], a.v[1][0], a.v[1][1]);
}

void propag(int u, int factor) {
    while(u) {
        int head = Nxt[u];
        int tail = Out[head];
        int par = Par[head];
        mat rez = AINT::query(In[head], In[tail]);
        //printf("u %d head %d tail %d par %d mat:\n", u, head, tail, par);
        afis(rez);
        //printf("---\n");
        CFD[par][0] += factor * min(min(rez.v[0][0], rez.v[0][1]), 1 + min(rez.v[1][0], rez.v[1][1]));
        CFD[par][1] += factor * min(1 + min(rez.v[0][0], rez.v[0][1]), min(rez.v[1][0], rez.v[1][1]));
        if(factor == 1) recalc_mat(par);
        u = par;
    }
}

void update(int u) {
    //printf("Update la %d cu tip %d\n", u, TipHut[u]);
    propag(u, -1);
    recalc_mat(u);
    propag(u, 1);
}

void dfs_sz(int u, int p) {
    Sz[u] = 1;
    for(auto &it : L[u]) if(it != p) {
        dfs_sz(it, u);
        Sz[u] += Sz[it];
        if(L[u][0] == p || Sz[it] > Sz[L[u][0]]) swap(it, L[u][0]);
    }
}

void dfs_hld(int u, int p) {
    Par[u] = p;
    In[u] = ++tmr;
    if(p) {
        Nxt[u] = (u == L[p][0] ? Nxt[p] : u);
    } else Nxt[u] = u;
    Out[Nxt[u]] = u;
    for(auto it : L[u])
        if(it != p) dfs_hld(it, u);
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(int i = 0; i <= n; ++i)
        TipHut[i] = 2;
    for(int i = 0; i < int(A.size()); ++i)
        L[A[i]].push_back(B[i]), L[B[i]].push_back(A[i]);
    dfs_sz(1, 0);
    AINT::init();
    dfs_hld(1, 0);
    AINT::len = tmr;
    //printf("Nod %d S %d N %d P %d I %d\n", i, Sz[i], Nxt[i], Par[i], In[i]);
}


int rez() {
    return min(CFD[0][0], CFD[0][1]);
}
int cat(int v) {
    TipHut[v] = 0;
    update(v);
    return rez();
}

int dog(int v) {
    TipHut[v] = 1;
    update(v);
    return rez();
}

int neighbor(int v) {
    TipHut[v] = 2;
    update(v);
    return rez();
}

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