Submission #239156

#	Time	Username	Problem	Language	Result	Execution time	Memory
239156		karma	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1319 ms	28408 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = (int)1e5 + 2;
const int inf = 2e5;

int n, u, v, q, sz[N], cur[N], par[N], t, tail[N];
int cnt, cntp, head[N], pos[N], id[N], big[N];
vector<int> adj[N];

int l[N << 2], h[N << 2];
struct TNode {
    int g[2][2];
    TNode() {g[0][0] = g[1][1] = 0, g[1][0] = g[0][1] = inf;}
    TNode operator +(const TNode& r)const& {
         TNode res;
         res.g[0][0] = min({g[0][1] + r.g[1][0], g[0][1] + r.g[0][0] + 1, g[0][0] + r.g[0][0], g[0][0] + r.g[1][0] + 1, inf});
         res.g[0][1] = min({g[0][1] + r.g[1][1], g[0][1] + r.g[0][1] + 1, g[0][0] + r.g[0][1], g[0][0] + r.g[1][1] + 1, inf});
         res.g[1][0] = min({g[1][1] + r.g[1][0], g[1][1] + r.g[0][0] + 1, g[1][0] + r.g[0][0], g[1][0] + r.g[1][0] + 1, inf});
         res.g[1][1] = min({g[1][1] + r.g[1][1], g[1][1] + r.g[0][1] + 1, g[1][0] + r.g[0][1], g[1][0] + r.g[1][1] + 1, inf});
         return res;
    }
} st[N << 2], val;

void build(int x, int low, int high) {
    l[x] = low, h[x] = high;
    if(low == high) return;
    int mid = (low + high) >> 1;
    build(x << 1, low, mid);
    build(x << 1 | 1, mid + 1, high);
}

void upd(int x, int pos, int add0, int add1) {
    if(l[x] > pos || h[x] < pos) return;
    if(l[x] == pos && h[x] == pos) {
        st[x].g[0][0] += add0;
        st[x].g[1][1] += add1;
        return;
    }
    upd(x << 1, pos, add0, add1);
    upd(x << 1 | 1, pos, add0, add1);
    st[x] = st[x << 1] + st[x << 1 | 1];
}

TNode get(int x, int low, int high) {
    if(low > high) return TNode();
    if(low > h[x] || l[x] > high) return TNode();
    if(low <= l[x] && h[x] <= high) return st[x];
    return get(x << 1, low, high) + get(x << 1 | 1, low, high);
}

void hld(int u) {
    if(!head[cnt]) head[cnt] = u;
    id[u] = cnt, pos[u] = ++cntp, tail[cnt] = u;
    for(int v: adj[u])
        if(!big[u] || sz[v] > sz[big[u]]) big[u] = v;
    if(big[u]) hld(big[u]);
    for(int v: adj[u])
        if(big[u] != v) ++cnt, hld(v);
}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    for(int i = 0; i < A.size(); ++i) {
        adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
    }
    function<void(int)> dfs = [&](int u) {
        sz[u] = 1;
        for(int& v: adj[u]) {
            if(v == par[u]) swap(v, adj[u].back());
            if(v == par[u]) continue;
            par[v] = u;
            dfs(v);
            sz[u] += sz[v];
        }
        if(par[u]) adj[u].pop_back();
    };
    dfs(1), cnt = 1, hld(1);
    build(1, 1, n);
    fill(cur, cur + n + 1, -1);
}

int f0, f1, top, nf0, nf1;
pair<int, int> getf(int l, int r) {
    val = get(1, pos[l], pos[r]);
    return mp(min({val.g[0][0], val.g[0][1], val.g[1][0] + 1, val.g[1][1] + 1}),
              min({val.g[1][0], val.g[1][1], val.g[0][0] + 1, val.g[0][1] + 1}));
}
void update(int v, int add0, int add1) {
     while(1) {
        top = head[id[v]];
        tie(f0, f1) = getf(top, tail[id[v]]);
        upd(1, pos[v], add0, add1);
        tie(nf0, nf1) = getf(top, tail[id[v]]);
        if(top == 1) return;
        add0 = nf0 - f0, add1 = nf1 - f1, v = par[top];
     }
}

int getans() {
    tie(f0, f1) = getf(1, tail[1]);
    return min(f0, f1);
}

int cat(int v) {
   cur[v] = 0;
   update(v, 0, inf);
   return getans();
}

int dog(int v) {
   cur[v] = 1;
   update(v, inf, 0);
   return getans();
}

int neighbor(int v) {
   if(cur[v] == 1) update(v, -inf, 0);
   else if(cur[v] == 0) update(v, 0, -inf);
   cur[v] = -1;
   return getans();
}

Compilation message (stderr)

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

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