Submission #1103065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103065		ProgrammerAlex	Cats or Dogs (JOI18_catdog)	C++17	Compilation error	0 ms	0 KiB

catdog

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 100005;

vector<int> tree[MAX_N];
int N, Q;

// HLD variables
int parent[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], pos[MAX_N];
int curr_pos = 0;

// Segment Tree variables
struct Node {
    int cats, dogs;
} segTree[4 * MAX_N];

int cats_in_node[MAX_N], dogs_in_node[MAX_N]; // Counts at nodes
int total_cats = 0, total_dogs = 0;
int danger_level = 0; // Total number of candidate edges

// Read input efficiently
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

// DFS to compute sizes and heavy child
int dfs(int u, int p) {
    int size = 1;
    int max_subtree = 0;
    parent[u] = p;
    for (int v : tree[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            int subtree_size = dfs(v, u);
            size += subtree_size;
            if (subtree_size > max_subtree) {
                max_subtree = subtree_size;
                heavy[u] = v;
            }
        }
    }
    return size;
}

// Decompose the tree
void decompose(int u, int h) {
    head[u] = h;
    pos[u] = curr_pos++;
    if (heavy[u] != -1) {
        decompose(heavy[u], h);
    }
    for (int v : tree[u]) {
        if (v != parent[u] && v != heavy[u]) {
            decompose(v, v);
        }
    }
}

// Build the segment tree
void build_segTree(int node, int l, int r) {
    segTree[node] = {0, 0};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build_segTree(2 * node, l, mid);
    build_segTree(2 * node + 1, mid + 1, r);
}

// Update the segment tree
void update_segTree(int node, int l, int r, int idx, int cat_diff, int dog_diff) {
    if (l == r) {
        segTree[node].cats += cat_diff;
        segTree[node].dogs += dog_diff;
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) {
        update_segTree(2 * node, l, mid, idx, cat_diff, dog_diff);
    } else {
        update_segTree(2 * node + 1, mid + 1, r, idx, cat_diff, dog_diff);
    }
    segTree[node].cats = segTree[2 * node].cats + segTree[2 * node + 1].cats;
    segTree[node].dogs = segTree[2 * node].dogs + segTree[2 * node + 1].dogs;
}

// Query counts in a path
Node query_segTree(int node, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return {0, 0};
    if (ql <= l && r <= qr) {
        return segTree[node];
    }
    int mid = (l + r) / 2;
    Node left = query_segTree(2 * node, l, mid, ql, qr);
    Node right = query_segTree(2 * node + 1, mid + 1, r, ql, qr);
    return {left.cats + right.cats, left.dogs + right.dogs};
}

// Update counts along the path
void update_counts(int u, int cat_diff, int dog_diff) {
    while (u != -1) {
        update_segTree(1, 0, N - 1, pos[u], cat_diff, dog_diff);
        u = parent[head[u]];
    }
}

// Check and update candidate edges
void update_danger_level(int u, int cat_diff, int dog_diff) {
    int prev_cats = cats_in_node[u];
    int prev_dogs = dogs_in_node[u];
    cats_in_node[u] += cat_diff;
    dogs_in_node[u] += dog_diff;

    bool prev_zero = (prev_cats == 0 && prev_dogs == 0);
    bool curr_zero = (cats_in_node[u] == 0 && dogs_in_node[u] == 0);

    if (prev_zero != curr_zero && parent[u] != -1) {
        // Edge between u and parent[u] may change status
        int u_cats = cats_in_node[u];
        int u_dogs = dogs_in_node[u];
        int p_cats = cats_in_node[parent[u]];
        int p_dogs = cats_in_node[parent[u]];

        Node total = query_segTree(1, 0, N - 1, 0, N - 1);

        int cats_in_subtree = cats_in_node[u];
        int dogs_in_subtree = dogs_in_node[u];
        int cats_out_subtree = total_cats - cats_in_subtree;
        int dogs_out_subtree = total_dogs - dogs_in_subtree;

        bool was_candidate = false;
        bool now_candidate = false;

        // Previous status
        if ((prev_cats > 0 && prev_dogs == 0 && dogs_out_subtree > 0) ||
            (prev_dogs > 0 && prev_cats == 0 && cats_out_subtree > 0)) {
            was_candidate = true;
        }

        // Current status
        if ((cats_in_node[u] > 0 && dogs_in_node[u] == 0 && (total_dogs - dogs_in_node[u]) > 0) ||
            (dogs_in_node[u] > 0 && cats_in_node[u] == 0 && (total_cats - cats_in_node[u]) > 0)) {
            now_candidate = true;
        }

        if (was_candidate && !now_candidate) {
            danger_level--;
        } else if (!was_candidate && now_candidate) {
            danger_level++;
        }
    }
}

// Initialize function
void initialize(int n, int A[], int B[]) {
    N = n;
    memset(heavy, -1, sizeof(heavy));
    memset(cats_in_node, 0, sizeof(cats_in_node));
    memset(dogs_in_node, 0, sizeof(dogs_in_node));

    for (int i = 0; i < N - 1; ++i) {
        int u = A[i];
        int v = B[i];
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    parent[0] = -1;
    depth[0] = 0;
    dfs(0, -1);
    decompose(0, 0);

    build_segTree(1, 0, N - 1);
}

// Cat function
int cat(int v) {
    total_cats++;
    update_counts(v, 1, 0);

    int u = v;
    while (u != -1) {
        update_danger_level(u, 1, 0);
        u = parent[u];
    }

    return danger_level;
}

// Dog function
int dog(int v) {
    total_dogs++;
    update_counts(v, 0, 1);

    int u = v;
    while (u != -1) {
        update_danger_level(u, 0, 1);
        u = parent[u];
    }

    return danger_level;
}

// Neighbor function
int neighbor(int v) {
    if (cats_in_node[v] > 0) {
        total_cats--;
        update_counts(v, -1, 0);

        int u = v;
        while (u != -1) {
            update_danger_level(u, -1, 0);
            u = parent[u];
        }
    } else if (dogs_in_node[v] > 0) {
        total_dogs--;
        update_counts(v, 0, -1);

        int u = v;
        while (u != -1) {
            update_danger_level(u, 0, -1);
            u = parent[u];
        }
    }
    return danger_level;
}

// Main function
int main() {
    fast_io();

    int n;
    cin >> n;
    int A[MAX_N], B[MAX_N];
    for (int i = 0; i < n - 1; ++i) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    initialize(n, A, B);

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int T, v;
        cin >> T >> v;
        v--;
        int res;
        if (T == 1) {
            res = cat(v);
        } else if (T == 2) {
            res = dog(v);
        } else {
            res = neighbor(v);
        }
        cout << res << endl;
    }

    return 0;
}

Compilation message (stderr)

catdog.cpp: In function 'void update_danger_level(int, int, int)':
catdog.cpp:125:13: warning: unused variable 'u_cats' [-Wunused-variable]
  125 |         int u_cats = cats_in_node[u];
      |             ^~~~~~
catdog.cpp:126:13: warning: unused variable 'u_dogs' [-Wunused-variable]
  126 |         int u_dogs = dogs_in_node[u];
      |             ^~~~~~
catdog.cpp:127:13: warning: unused variable 'p_cats' [-Wunused-variable]
  127 |         int p_cats = cats_in_node[parent[u]];
      |             ^~~~~~
catdog.cpp:128:13: warning: unused variable 'p_dogs' [-Wunused-variable]
  128 |         int p_dogs = cats_in_node[parent[u]];
      |             ^~~~~~
catdog.cpp:130:14: warning: variable 'total' set but not used [-Wunused-but-set-variable]
  130 |         Node total = query_segTree(1, 0, N - 1, 0, N - 1);
      |              ^~~~~
/usr/bin/ld: /tmp/ccSomzCi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuHm4ui.o:catdog.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccSomzCi.o: in function `main':
grader.cpp:(.text.startup+0x1e2): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status