Submission #1173514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173514		_callmelucian	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	3 ms	4932 KiB

catdog

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int INF = 1e9;

struct node : vector<vector<int>> {
    node() : vector<vector<int>>(2, vector<int>(2, INF)) {}
    node (int a, int b, int c, int d) : vector<vector<int>>({{a, b}, {c, d}}) {}

    const node operator + (const node &o) {
        if ((*this) == node()) return o;
        if (o == node()) return (*this);

        node ans;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                ans[i][j] = INF;
                for (int s1 = 0; s1 < 2; s1++)
                    for (int s2 = 0; s2 < 2; s2++)
                        if (max(o[s2][j], (*this)[i][s1]) != INF)
                            ans[i][j] = min(ans[i][j], (*this)[i][s1] + o[s2][j] + (s1 ^ s2));
            }
        }
        return ans;
    }

    int minElement() {
        int ans = INT_MAX;
        for (vector<int> &v : (*this))
            ans = min(ans, *min_element(all(v)));
        return ans;
    }
};

const vector<node> base = { node(0, INF, INF, 0),
                            node(0, INF, INF, INF),
                            node(INF, INF, INF , 0) };

struct IT {
    vector<node> tr;
    IT (int sz = 0) : tr(4 * sz) {}

    void update (int pos, node cur, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }
        tr[k] = cur;
        for (k >>= 1; k > 0; k >>= 1)
            tr[k] = tr[k << 1] + tr[k << 1 | 1];
    }

    node getNode() { return tr[1]; }
} tree[mn];

int depth[mn], sz[mn], par[mn], sumChild[2][mn], n;
int chain[mn], chainSz[mn], type[mn];
vector<int> adj[mn];

int szDfs (int u, int p) {
    sz[u] = 1;
    for (int v : adj[u])
        if (v != p) sz[u] += szDfs(v, u);
    return sz[u];
}

void dfs (int u, int p, int d, bool toP) {
    if (u == 1) szDfs(u, p);
    chain[u] = (toP ? chain[p] : u), chainSz[chain[u]]++;
    par[u] = p, depth[u] = d;

    sort(all(adj[u]), [&] (int a, int b) { return sz[a] > sz[b]; });
    bool heavy = 1;
    for (int v : adj[u])
        if (v != p) dfs(v, u, d + 1, heavy), heavy = 0;
}

void modify (int u) {
    while (u) {
        // pre-calculate some information for current node
        int head = chain[u], sz = chainSz[head], id = depth[u] - depth[head] + 1;
        node cur = tree[head].getNode();

        // remove contribution to sumChild[...][par[head]]
        sumChild[0][par[head]] -= min(min(cur[0][0], cur[0][1]), min(cur[1][0], cur[1][1]) + 1);
        sumChild[1][par[head]] -= min(min(cur[1][0], cur[1][1]), min(cur[0][0], cur[0][1]) + 1);

        // update current node
        cur = base[type[u]];
        if (cur[0][0] != INF) cur[0][0] += sumChild[0][u];
        if (cur[1][1] != INF) cur[1][1] += sumChild[1][u];
        tree[head].update(id, cur, 1, 1, sz);

        // re-add contribution to sumChild[...][par[head]]
        sumChild[0][par[head]] += min(min(cur[0][0], cur[0][1]), min(cur[1][0], cur[1][1]) + 1);
        sumChild[1][par[head]] += min(min(cur[1][0], cur[1][1]), min(cur[0][0], cur[0][1]) + 1);

        u = par[head];
    }
}

int solve() { return tree[1].getNode().minElement(); }

int neighbor (int u) {
    type[u] = 0, modify(u);
    return solve();
}

int cat (int u) {
    type[u] = 1, modify(u);
    return solve();
}

int dog (int u) {
    type[u] = 2, modify(u);
    return solve();
}

void initialize (int n, vector<int> a, vector<int> b) {
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    dfs(1, 0, 1, 0);
    for (int i = 1; i <= n; i++) {
        if (chain[i] != i) continue;
        tree[i] = IT(chainSz[i]);
        for (int j = 1; j <= chainSz[i]; j++)
            tree[i].update(j, base[0], 1, 1, chainSz[i]);
    }
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    initialize(5, {1, 2, 2, 4}, {2, 3, 4, 5});

    cout << cat(3) << " " << dog(5) << "\n";
    cout << cat(2) << " " << dog(1) << "\n";
    cout << neighbor(2) << "\n";

    return 0;
}
#endif // LOCAL

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