Submission #1326646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326646		DeathIsAwe	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	1149 ms	32928 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int parent[100001], depth[100001], heavy[100001], head[100001], pos[100001], revpos[100001], tail[100001];
vector<vector<int>> segment; //0 is dog dog, 1 is dog cat, 2 is cat dog, 3 is cat cat
vector<vector<int>> graph;
int curpos = 0, bottom = 0;


vector<int> merge(vector<int> a, vector<int> b) {
    if (a[0] == -1) return b;
    if (b[0] == -1) return a;
    //cout << "MERGE" << endl;
    //for (int i: a) cout << i << ' '; cout << endl;
    //for (int i: b) cout << i << ' '; cout << endl;
    vector<int> bruh(4);
    bruh[0] = min(a[0] + b[0], min(a[0] + b[2] + 1, min(a[1] + b[0] + 1, a[1] + b[2])));
    bruh[1] = min(a[0] + b[1], min(a[0] + b[3] + 1, min(a[1] + b[1] + 1, a[1] + b[3])));
    bruh[2] = min(a[2] + b[0], min(a[2] + b[2] + 1, min(a[3] + b[0] + 1, a[3] + b[2])));
    bruh[3] = min(a[2] + b[1], min(a[2] + b[3] + 1, min(a[3] + b[1] + 1, a[3] + b[3])));
    for (int i=0;i<4;i++) bruh[i] = min(1010000000, bruh[i]);
    
    //for (int i: bruh) cout << i << ' '; cout << endl;
    return bruh;
}


void change(int pos, vector<int> val) {
    pos += 131072;
    segment[pos] = val;
    while (pos > 1) {
        pos /= 2;
        segment[pos] = merge(segment[2 * pos], segment[2 * pos + 1]);
    }
}


vector<int> segquery(int a, int b) {
    if (a > b) swap(a, b);
    a += 131072; b += 131072;
    vector<int> left(4, -1), right(4, -1);
    while (a <= b) {
        if (a % 2 == 1) left = merge(left, segment[a++]);
        if (b % 2 == 0) right = merge(segment[b--], right);
        a /= 2; b /= 2;
    }
    return merge(left, right);
}


int dfs(int v) {
    int size = 1;
    int max_c_size = 0;
    for (int c : graph[v]) {
        if (c != parent[v]) {
            parent[c] = v; depth[c] = depth[v] + 1;
            int c_size = dfs(c);
            size += c_size;
            if (c_size > max_c_size) max_c_size = c_size, heavy[v] = c;
        }
    }
    return size;
}


void decompose(int v, int h) {
    head[v] = h, pos[v] = curpos, revpos[curpos++] = v;
    if (heavy[v] != -1) decompose(heavy[v], h);
    for (int i : graph[v]) {
        if (i != parent[v] && i != heavy[v]) decompose(i, i);
    }
}


void process(int a, vector<int> newval) {
    vector<int> oldgroup = segquery(pos[tail[a]], pos[head[a]]);
    change(pos[a], newval);
    vector<int> newgroup = segquery(pos[tail[a]], pos[head[a]]);
    if (head[a] == 0) return;
    //cout << a << ' ' << tail[a] << ' ' << head[a] << ' ' << "ORIGINALVAL" << endl;
    //for (int i: segment[pos[a] + 131072]) cout << i << ' '; cout << endl;
    //cout << "OLDGROUP" << a << endl;
    //for (int i: oldgroup) cout << i << ' '; cout << endl;
    //cout << "NEWGROUP" << a << endl;
    //for (int i: newgroup) cout << i << ' '; cout << endl;
    //cout << "==================" << endl;
    int olddog = min(oldgroup[0], min(oldgroup[1], min(oldgroup[2] + 1, oldgroup[3] + 1)));
    int oldcat = min(oldgroup[0] + 1, min(oldgroup[1] + 1, min(oldgroup[2], oldgroup[3])));
    int newdog = min(newgroup[0], min(newgroup[1], min(newgroup[2] + 1, newgroup[3] + 1)));
    int newcat = min(newgroup[0] + 1, min(newgroup[1] + 1, min(newgroup[2], newgroup[3])));
    vector<int> changevec = segment[pos[parent[head[a]]] + 131072];
    changevec[0] += newdog - olddog, changevec[3] += newcat - oldcat;
    process(parent[head[a]], changevec);
}


void initialize(int n, vector<int> arra, vector<int> arrb) {
    for (int i=0;i<n;i++) heavy[i] = -1;
    graph = vector<vector<int>> (n);
    for (int i=0;i<n-1;i++) {
        arra[i]--; arrb[i]--;
        graph[arra[i]].pb(arrb[i]);
        graph[arrb[i]].pb(arra[i]);
    }
    parent[0] = 0, depth[0] = 1;
    dfs(0); decompose(0, 0);
    //for (int i=0;i<n;i++) cout << pos[i] << ' '; cout << endl;
    //for (int i=0;i<n;i++) cout << revpos[i] << ' '; cout << endl;
    int curtail = revpos[n - 1];
    tail[revpos[n - 1]] = curtail;
    for (int i=n-2;i>-1;i--) {
        if (head[revpos[i]] != head[revpos[i + 1]]) curtail = revpos[i];
        tail[revpos[i]] = curtail;
    }
    segment = vector<vector<int>> (262144, vector<int>(4) = {0, 1, 1, 0});
    for (int i=131072;i<262144;i++) segment[i][1] = 1000000000, segment[i][2] = 1000000000;
    for (int i=0;i<n;i++) if (head[i] == 0 && depth[i] > depth[bottom]) bottom = i;
    bottom = pos[bottom];
}

int cat(int v) {
    v -= 1;
    vector<int> lmao = segment[pos[v] + 131072]; lmao[0] += 1000000000; process(v, lmao);
    //for (int i: segment[pos[2] + 131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[pos[1] + 131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[pos[0] + 131072]) cout << i << ' '; cout << endl; cout << endl;
    lmao = segquery(0, bottom);
    return *min_element(lmao.begin(), lmao.end());
}

int dog(int v) {
    v -= 1;
    vector<int> lmao = segment[pos[v] + 131072]; lmao[3] += 1000000000; process(v, lmao);
    //for (int i: segment[6 + 131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[(4+131072)/2]) cout << i << ' '; cout << endl;
    //for (int i: segment[131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[131072/2]) cout << i << ' '; cout << endl;
    //for (int i: segment[131072/4]) cout << i << ' '; cout << endl; cout << endl;
    lmao = segquery(0, bottom);
    return *min_element(lmao.begin(), lmao.end());
}

int neighbor(int v) {
    v -= 1;
    vector<int> lmao = segment[pos[v] + 131072];
    if (lmao[0] >= 1000000000) lmao[0] -= 1000000000;
    else lmao[3] -= 1000000000;
    process(v, lmao);
    //for (int i: segment[pos[2] + 131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[pos[1] + 131072]) cout << i << ' '; cout << endl;
    //for (int i: segment[pos[0] + 131072]) cout << i << ' '; cout << endl; cout << endl;
    lmao = segquery(0, bottom);
    return *min_element(lmao.begin(), lmao.end());
}

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