Submission #253899

#	Time	Username	Problem	Language	Result	Execution time	Memory
253899		IgorI	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	361 ms	107304 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9;
const int N = 100002;

struct Table{
    ll a[2][2];
};

struct Sollution{
    vector<Table> tree;
    void build(int L, int R, int V)
    {
        if (L + 1 == R)
        {
            tree[V].a[0][0] = 0;
            tree[V].a[0][1] = INF;
            tree[V].a[1][0] = INF;
            tree[V].a[1][1] = 0;
            return;
        }
        tree[V].a[0][0] = 0;
        tree[V].a[1][0] = 1;
        tree[V].a[0][1] = 1;
        tree[V].a[1][1] = 0;
        int M = (L + R) / 2;
        build(L, M, 2 * V + 1);
        build(M, R, 2 * V + 2);
    }
    Sollution(int _n)
    {
        tree.resize(4 * _n);
        build(0, _n, 0);
    }
    void __Change(int pos, int cost0, int cost1, int L, int R, int V)
    {
        if (L + 1 == R)
        {
            tree[V].a[0][0] += cost0;
            tree[V].a[1][1] += cost1;
            return;
        }
        int M = (L + R) / 2;
        if (pos < M) __Change(pos, cost0, cost1, L, M, 2 * V + 1);
        else __Change(pos, cost0, cost1, M, R, 2 * V + 2);
        for (int le = 0; le < 2; le++)
        {
            for (int ri = 0; ri < 2; ri++)
            {
                tree[V].a[le][ri] = min(min(tree[2 * V + 1].a[le][0] + tree[2 * V + 2].a[0][ri],
                                            tree[2 * V + 1].a[le][1] + tree[2 * V + 2].a[1][ri]),
                                        min(tree[2 * V + 1].a[le][0] + tree[2 * V + 2].a[1][ri] + 1,
                                            tree[2 * V + 1].a[le][1] + tree[2 * V + 2].a[0][ri] + 1));
            }
        }
    }
    void Change(int pos, int cost0, int cost1)
    {
        __Change(pos, cost0, cost1, 0, tree.size() / 4, 0);
    }
    Table Cost()
    {
        return tree[0];
    }
};

ll n;
vector<int> graph[N];
ll x[N];
ll papa[N];
ll sz[N];

int main_child[N];
vector<int> other_child[N];
vector<vector<int> > route;
vector<Sollution> hld;
int route_pos[N];
int route_id[N];

void dfs1(int v, int p)
{
    papa[v] = p;
    sz[v] = 1;
    for (auto u : graph[v]) if (u != p)
    {
        dfs1(u, v);
        sz[v] += sz[u];
    }
}

void dfs2(int v, int p)
{
    int mxsz = 0, id = -1;
    for (auto u : graph[v]) if (u != p)
    {
        if (sz[u] > mxsz)
        {
            mxsz = sz[u];
            id = u;
        }
    }
    main_child[v] = id;
    for (auto u : graph[v]) if (u != p)
    {
        dfs2(u, v);
        if (u != id) other_child[v].push_back(u);
    }
}

ll answer()
{
    ll x = INF;
    Table T = hld[0].Cost();
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            x = min(x, T.a[i][j]);
        }
    }
    return x;
}

void initialize(int n0, vector<int> a, vector<int> b)
{
    n = n0;
    for (int i = 0; i < n - 1; i++)
    {
        a[i]--, b[i]--;
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        x[i] = -1;
    }
    dfs1(0, 0);
    dfs2(0, 0);
    for (int i = 0; i < n; i++)
    {
        route_id[i] = -1;
        route_pos[i] = -1;
    }
    for (int i = 0; i < n; i++)
    {
        if (route_id[i] == -1)
        {
            vector<int> r;
            int x = i;
            while (x != -1)
            {
                r.push_back(x);
                x = main_child[x];
            }
            for (int j = 0; j < r.size(); j++)
            {
                route_id[r[j]] = route.size();
                route_pos[r[j]] = j;
            }
            route.push_back(r);
            hld.push_back(Sollution(r.size()));
        }
    }
}

void Change(int v, int cost0, int cost1)
{
    int x = route_id[v];
    int y = route_pos[v];
    Table oldT = hld[x].Cost();
    int oldminc0 = min(oldT.a[0][0], oldT.a[0][1]);
    int oldminc1 = min(oldT.a[1][0], oldT.a[1][1]);
    int oldd0 = min(oldminc0, oldminc1 + 1);
    int oldd1 = min(oldminc0 + 1, oldminc1);
    hld[x].Change(y, cost0, cost1);
    Table T = hld[x].Cost();
    int minc0 = min(T.a[0][0], T.a[0][1]);
    int minc1 = min(T.a[1][0], T.a[1][1]);
    int d0 = min(minc0, minc1 + 1);
    int d1 = min(minc0 + 1, minc1);
    v = route[x][0];
    if (v == 0) return;
    v = papa[v];
    Change(v, d0 - oldd0, d1 - oldd1);
}

int cat(int v)
{
    v--;
    x[v] = 0;
    Change(v, 0, INF);
    return answer();
}

int dog(int v)
{
    v--;
    x[v] = 1;
    Change(v, INF, 0);
    return answer();
}

int neighbor(int v)
{
    v--;
    if (x[v] == 0) Change(v, 0, -INF);
    if (x[v] == 1) Change(v, -INF, 0);
    x[v] = -1;
    return answer();
}

#ifdef LOCAL
int main()
{
    int n;
    cin >> n;
    vector<int> a(n - 1), b(n - 1);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a[i] >> b[i];
    }
    initialize(n, a, b);
    int q;
    cin >> q;
    while (q--)
    {
        int t, v;
        cin >> t >> v;
        if (t == 1) cout << cat(v) << endl;
        if (t == 2) cout << dog(v) << endl;
        if (t == 3) cout << neighbor(v) << endl;
    }
}
#endif // LOCAL

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:159:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < r.size(); j++)
                             ~~^~~~~~~~~~

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