Submission #1097829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097829		Neco_arc	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	616 ms	36176 KiB

catdog

#include<catdog.h>

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Cats or Dogs"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng);
}


int n;
int cl[maxn], last[maxn];
int In[maxn], nex[maxn], par[maxn], siz[maxn];
vector<int> edges[maxn];

int dfs_siz(int u) {
    siz[u] = 1;
    for(int &v : edges[u]) {
        edges[v].erase(find(all(edges[v]), u));
        siz[u] += dfs_siz(v);

        if(siz[v] > siz[edges[u][0]]) swap(v, edges[u][0]);
    }
    return siz[u];
}

void dfs_hld(int u) {
    static int Time = 0;
    In[u] = ++Time;
    for(int v : edges[u]) {
        par[v] = u;
        nex[v] = v == edges[u][0] ? nex[u] : v;
        dfs_hld(v);
    }
}

struct IT {
    struct Node {
        int a[2][2];
        Node() { a[0][0] = a[1][1] = 0, a[0][1] = a[1][0] = 1e9; }

    } st[4 * maxn];

    Node cb(const Node &x, const Node &y) {
        Node ans; memset(ans.a, 60, sizeof ans.a);
        fi(i, 0, 1) fi(j, 0, 1) fi(u, 0, 1) fi(v, 0, 1) {
            ans.a[i][v] = min(ans.a[i][v], x.a[i][j] + y.a[u][v] + (j != u));
        }
        return ans;
    }

    void update(int x, int val0, int val1, int id = 1, int l = 1, int r = n) {
        if(l > x || r < x) return;
        if(l == r) {
            st[id].a[0][0] += val0, st[id].a[1][1] += val1;
            return;
        }

        int mid = (l + r) >> 1;
        update(x, val0, val1, _left), update(x, val0, val1, _right);
        st[id] = cb(st[id * 2], st[id * 2 + 1]);
    }

    Node get(int u, int v, int id, int l, int r) {
        if(l > v || r < u) return Node();
        if(u <= l && r <= v) return st[id];

        int mid = (l + r) >> 1;
        return cb(get(u, v, _left), get(u, v, _right));
    }

    void get(int u, int v, int &A, int &B) {
        Node p = get(u, v, 1, 1, n);
        int x0 = min(p.a[0][1], p.a[0][0]);
        int x1 = min(p.a[1][0], p.a[1][1]);

        A = min(x0, x1 + 1);
        B = min(x0 + 1, x1);
    }

} St;

void update(int u, int col, int dt0, int dt1) {
    cl[u] = col;
    while(u) {
        int old0, old1, nw0, nw1;
        St.get(In[nex[u]], last[nex[u]], old0, old1);
        St.update(In[u], dt0, dt1);
        St.get(In[nex[u]], last[nex[u]], nw0, nw1);

        dt0 = nw0 - old0, dt1 = nw1 - old1;
        u = par[nex[u]];
    }
}

int get() {
    int ans0, ans1; St.get(In[1], last[1], ans0, ans1);
    return min(ans0, ans1);
}

int cat(int u) {
    update(u, 0, 0, 1e9);
    return get();
}

int dog(int u) {
    update(u, 1, 1e9, 0);
    return get();
}

int neighbor(int u) {
    if(cl[u]) update(u, -1, -1e9, 0);
    else update(u, -1, 0, -1e9);

    return get();
}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    fi(i, 0, n - 2) {
        edges[A[i]].push_back(B[i]), edges[B[i]].push_back(A[i]);
    }

    nex[1] = 1;
    dfs_siz(1), dfs_hld(1);
    fi(i, 1, n) last[nex[i]] = max(last[nex[i]], In[i]);
}

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