Submission #955108

#	Time	Username	Problem	Language	Result	Execution time	Memory
955108		cristi_tanase	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3045 ms	21328 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 5, mod = 1e9 + 7, inf = 2e6;
int n, m;
vector<int> g[nmax], path[nmax];
int sz[nmax], heavy[nmax], depth[nmax], top[nmax], parent[nmax], pos[nmax], crtpos, bottom[nmax];

struct T {
    int cc, cd, dc, dd;
};

T aint[nmax * 4];

T combine(T x, T y) {
    T ans = {inf, inf, inf, inf};
    ans.cc = min({x.cc + y.cc, x.cc + y.dc + 1, x.cd + y.dc, x.cd + y.cc + 1});
    ans.cd = min({x.cc + y.cd, x.cc + y.dd + 1, x.cd + y.dd, x.cd + y.cd + 1});
    ans.dd = min({x.dd + y.dd, x.dd + y.cd + 1, x.dc + y.cd, x.dc + y.dd + 1});
    ans.dc = min({x.dd + y.dc, x.dd + y.cc + 1, x.dc + y.cc, x.dc + y.dc + 1});
    return ans;
}


void build(int node, int left, int right) {
    if (left == right) {
        aint[node].cc = aint[node].dd = 0;
        aint[node].cd = aint[node].dc = inf;
        return;
    }
    int mid = (left + right) / 2;
    build(node * 2, left, mid);
    build(node * 2 + 1, mid + 1, right);
//    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
    aint[node].cc = aint[node].dd = 0;
    aint[node].cd = aint[node].dc = 0;
}

void update(int node, int left, int right, int x, pair<int, int> y) {
    if (left == right) {
        aint[node].cc = y.first;
        aint[node].dd = y.second;
        return;
    }
    int mid = (left + right) / 2;
    if (x <= mid) update(node * 2, left, mid, x, y);
    else update(node * 2 + 1, mid + 1, right, x, y);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

void update(int x, pair<int, int> y) {
    update(1, 1, n, x, y);
}

T query(int node, int left, int right, int x, int y) {
    if (x <= left && right <= y) {
        return aint[node];
    }
    int mid = (left + right) / 2;
    if (x <= mid && y > mid) {
        return combine(query(node * 2, left, mid, x, y), query(node * 2 + 1, mid + 1, right, x, y));
    }
    if (x <= mid) {
        return query(node * 2, left, mid, x, y);
    }
    if (y > mid) {
        return query(node * 2 + 1, mid + 1, right, x, y);
    }
}

T query(int x, int y) {
    return query(1, 1, n, x, y);
}

void dfs1(int x, int par = 0) {
    sz[x] = 1;
    parent[x] = par;
    depth[x] = depth[par] + 1;
    int mx = 0;
    for (auto y: g[x]) {
        if (y == par) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        if (sz[y] > mx) {
            heavy[x] = y;
            mx = sz[y];
        }
    }
}

void decompose(int x, int crttop) {
    path[crttop].push_back(x);
    top[x] = crttop;
    pos[x] = ++crtpos;
    if (heavy[x]) {
        decompose(heavy[x], crttop);
    }
    for (auto y: g[x]) {
        if (y == parent[x]) continue;
        if (heavy[x] != y) {
            decompose(y, y);
        }
    }
}

pair<int, int> getval(int x) {
    pair<int, int> ans; // first - cc ; second - dd
    for (auto y: g[x]) {
        if (y == parent[x] || y == heavy[x]) continue;
        T crt = query(pos[top[y]], pos[bottom[y]]);
        ans.first += min({crt.cc, crt.cd, crt.dc + 1, crt.dd + 1});
        ans.second += min({crt.cc + 1, crt.cd + 1, crt.dc, crt.dd});
    }
    T tmp = query(pos[x], pos[x]);
    if (tmp.cc == inf) ans.first = inf;
    if (tmp.dd == inf) ans.second = inf;
    return ans;
}

void dfs(int x) {
    for (auto y: g[x]) {
        if (y == parent[x]) continue;
        dfs(y);
    }
    pair<int, int> ans = getval(x);
    update(pos[x], ans);
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N; m = A.size();
    for (int i = 0; i < m; i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    dfs1(1);
    decompose(1, 1);
    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        for (auto x: path[i]) {
            bottom[x] = path[i].back();
        }
    }
    dfs(1);
}

int cat(int x) {
    pair<int, int> crt = getval(x);
    update(pos[x], {crt.first, inf});
    x = parent[top[x]];
    while (x) {
        auto tmp = getval(x);
        update(pos[x], getval(x));
        x = parent[top[x]];
    }
    T ans = query(pos[top[1]], pos[bottom[1]]);
    return min({ans.cc, ans.cd, ans.dc, ans.dd});
}

int dog(int x) {
    pair<int, int> crt = getval(x);
    update(pos[x], {inf, crt.second});
    x = parent[top[x]];
    while (x) {
        update(pos[x], getval(x));
        x = parent[top[x]];
    }
    T ans = query(pos[top[1]], pos[bottom[1]]);
    return min({ans.cc, ans.cd, ans.dc, ans.dd});
}

int neighbor(int x) {
    update(pos[x], {0, 0});
    pair<int, int> crt = getval(x);
    update(pos[x], crt);
    x = parent[top[x]];
    while (x) {
        update(pos[x], getval(x));
        x = parent[top[x]];
    }
    T ans = query(pos[top[1]], pos[bottom[1]]);
    return min({ans.cc, ans.cd, ans.dc, ans.dd});
}

Compilation message (stderr)

catdog.cpp: In function 'int cat(int)':
catdog.cpp:154:14: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
  154 |         auto tmp = getval(x);
      |              ^~~
catdog.cpp: In function 'T query(int, int, int, int, int)':
catdog.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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