Submission #97655

#	Time	Username	Problem	Language	Result	Execution time	Memory
97655		Alexa2001	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1380 ms	30752 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int Nmax = 1e5 + 5, inf = 1e6;

int n, tip[Nmax];

class SegmentTree
{
    int *go[2][2];
public:
    void build(int nr)
    {
        int i, j;
        for(i=0; i<2; ++i)
            for(j=0; j<2; ++j)
                go[i][j] = new int [nr << 2];
    }

    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            go[0][0][node] = go[1][1][node] = 0;
            go[0][1][node] = go[1][0][node] = inf;
            return;
        }
        build(left_son, st, mid);
        build(right_son, mid+1, dr);
        go[0][0][node] = go[1][1][node] = 0;
        go[0][1][node] = go[1][0][node] = 1;
    }

    void update(int node, int st, int dr, int pos, int a1, int a2)
    {
        if(st == dr)
        {
            go[0][0][node] += a1;
            go[1][1][node] += a2;
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos, a1, a2);
            else update(right_son, mid+1, dr, pos, a1, a2);

        int i, j, k, t;
        for(i=0; i<2; ++i)
            for(j=0; j<2; ++j)
            {
                int x = 10 * inf;
                for(k=0; k<2; ++k)
                    for(t=0; t<2; ++t)
                        x = min(x, go[i][k][left_son] + go[t][j][right_son] + (k != t));
                go[i][j][node] = x;
            }
    }

    int query0()
    {
        return min(go[0][0][1], go[0][1][1]);
    }
    int query1()
    {
        return min(go[1][0][1], go[1][1][1]);
    }
    int query()
    {
        return min(query1(), query0());
    }

} aint[Nmax];

namespace hp
{
    vector<int> v[Nmax], chain[Nmax];
    int nr = 0;
    int w[Nmax], t[Nmax], pos[Nmax], where[Nmax];

    void dfs(int node, int dad = 0)
    {
        w[node] = 1; t[node] = dad;
        for(auto it : v[node])
            if(it != dad)
            {
                w[node] += w[it];
                dfs(it, node);
            }
    }

    void make_chains(int node)
    {
        where[node] = nr;
        pos[node] = chain[nr].size();
        chain[nr].push_back(node);

        int xson = -1;
        for(auto it : v[node])
            if(it != t[node] && (xson == -1 || w[xson] < w[it])) xson = it;

        if(xson == -1) return;

        make_chains(xson);

        for(auto it : v[node])
            if(it != t[node] && it != xson)
            {
                ++nr;
                make_chains(it);
            }
    }

    void prepare()
    {
        dfs(1);
        nr = 1; make_chains(1);
        int i;
        for(i=1; i<=nr; ++i)
        {
            aint[i].build(chain[i].size());
            aint[i].build(1, 0, chain[i].size() - 1);
        }
    }

    void update(int node, int add1, int add2)
    {
        int T, ans0, ans1;
        int C = where[node];
        T = t[chain[C][0]];

        if(T)
            ans0 = aint[C].query0(), ans1 = aint[C].query1();

        aint[C].update(1, 0, chain[C].size() - 1, pos[node], add1, add2);

        if(!T) return;

        int ans2, ans3;
        ans2 = aint[C].query0();
        ans3 = aint[C].query1();

        update(T, min(ans2, ans3 + 1) - min(ans0, ans1 + 1), min(ans2 + 1, ans3) - min(ans0 + 1, ans1));
    }
}

void initialize(int N, vector<int> A, vector<int> B)
{
    int i;
    n = N;
    for(i=0; i<n-1; ++i)
    {
        hp :: v[A[i]].push_back(B[i]);
        hp :: v[B[i]].push_back(A[i]);
    }
    hp :: prepare();
}

int cat(int v) /// tip 1
{
    hp :: update(v, 0, inf);
    tip[v] = 1;
    return aint[1].query();
}

int dog(int v) /// tip 2
{
    hp :: update(v, inf, 0);
    tip[v] = 2;
    return aint[1].query();
}

int neighbor(int v) /// tip 0
{
    if(tip[v] == 1) hp :: update(v, 0, -inf);
        else hp :: update(v, -inf, 0);
    tip[v] = 0;
    return aint[1].query();
}

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