Кольорові обмеження#13096

Кольорові обмеження (Розбір)

Ідея

Для кожного кольору $c$ потрібно видалити всі ребра цього кольору та знайти мінімальну вартість виконання решти XOR-обмежень.

Спочатку розглянемо фіксований набір ребер.

Кожне ребро задає обмеження вигляду

x_{u} \oplus x_{v} = b .

x_u\oplus x_v=b.

Якщо ми знаємо значення однієї вершини у компоненті зв'язності, то значення всіх інших вершин однозначно визначаються обмеженнями.

Отже, кожна компонента зв'язності має не більше двох можливих розфарбувань: коли значення вибраного кореня дорівнює $0$ або $1$ .

Якщо обмеження суперечать одне одному, допустимого розфарбування не існує.

Цю інформацію можна підтримувати за допомогою DSU з XOR-парностями.

Проте будувати DSU заново для кожного кольору було б занадто повільно.

Ключове спостереження

Замість того щоб незалежно видаляти ребра кожного кольору, можна обробити всі кольори за допомогою методу розділяй і володарюй.

Нехай зараз ми обчислюємо відповіді для кольорів із відрізка $[l, r]$ [l,r].

Будемо підтримувати DSU, у якому вже враховано всі ребра, кольори яких не належать цьому відрізку.

Позначимо $mi d = (l + r) /2$ mid=(l+r)/2.

Щоб знайти відповіді для кольорів із $[l, mi d]$ [l,mid], потрібно врахувати всі ребра з кольорами із $[mi d + 1, r]$ [mid+1,r], адже жоден із цих кольорів ми не видалятимемо.

Аналогічно, для кольорів із $[mi d + 1, r]$ [mid+1,r] потрібно врахувати всі ребра з кольорами із $[l, mi d]$ [l,mid].

Отже, можемо діяти таким чином:

Додати всі ребра кольорів із $[mi d + 1, r]$ [mid+1,r] та рекурсивно розв'язати ліву половину.
Відкотити DSU до попереднього стану.
Додати всі ребра кольорів із $[l, mi d]$ [l,mid] та рекурсивно розв'язати праву половину.
Знову відкотити DSU.

Коли дійдемо до відрізка $l = r = c$ l=r=c, у DSU будуть враховані рівно ті ребра, колір яких відрізняється від $c$ .

Тобто отримаємо саме той граф, для якого потрібно знайти відповідь.

Кожне ребро додається не більше одного разу на кожному рівні рекурсії, тому сумарно виконаємо $O (m lo g k)$ O(m\log k) операцій DSU.

Розв'язок

Використаємо DSU з відкатами.

Для кожної вершини $v$ будемо зберігати:

$p_{v}$ p_v — батька вершини у DSU.
$s z_{v}$ sz_v — розмір компоненти, якщо $v$ є її коренем.
$x r_{v}$ xr_v — XOR-різницю між значеннями вершини $v$ та її батька у DSU.

Під час пошуку кореня вершини також будемо обчислювати XOR-різницю між значеннями вершини та кореня.

Стиснення шляхів використовувати не будемо, оскільки нам потрібно вміти відкотити зміни. Натомість будемо приєднувати меншу компоненту до більшої.

Підтримка мінімальної вартості

Для кожного кореня DSU $u$ позначимо через $cos t_{u} [t]$ cost_u[t] мінімальну вартість виконання всіх обмежень усередині його компоненти за умови, що кінцеве значення кореня дорівнює $t$ .

Спочатку кожна вершина утворює окрему компоненту.

Тому

cos t_{i} [t] = {0, w_{i}, t = a_{i}, t \neq = a_{i} .

cost_i[t]= \begin{cases} 0, & t=a_i,\\ w_i, & t\ne a_i. \end{cases}

Мінімальна вартість для всього графа дорівнює

c u r = корені DSU u \sum min (cos t_{u} [0], cos t_{u} [1]) .

cur=\sum_{\text{корені DSU }u} \min(cost_u[0],cost_u[1]).

Тепер нехай ми додаємо ребро $(u, v)$ з обмеженням $x_{u} \oplus x_{v} = b$ x_u\oplus x_v=b.

Позначимо через $U, V$ корені компонент вершин $u, v$ , а через $s_{u}, s_{v}$ s_u,s_v — їхні XOR-різниці відносно відповідних коренів.

Тоді необхідна XOR-різниця між коренями дорівнює

d = s_{u} \oplus s_{v} \oplus b .

d=s_u\oplus s_v\oplus b.

Якщо $U = V$ U=V, достатньо перевірити, чи задовольняє вже встановлена парність нове обмеження.

Якщо ні, то система обмежень стає суперечливою.

Інакше потрібно об'єднати дві компоненти.

Нехай корінь $V$ приєднується до кореня $U$ . Тоді

x_{V} = x_{U} \oplus d .

x_V=x_U\oplus d.

Отже, нові вартості об'єднаної компоненти дорівнюють

cos t_{U}^{'} [t] = cos t_{U} [t] + cos t_{V} [t \oplus d] .

cost_U'[t]=cost_U[t]+cost_V[t\oplus d].

Оновимо $c u r$ : віднімемо внески двох старих компонент та додамо внесок нової компоненти.

Усі ці обчислення після знаходження коренів виконуються за $O (1)$ .

Відкати DSU

Перед переходом у рекурсивну гілку зберігатимемо поточний стан DSU.

Для кожного успішного об'єднання запам'ятаємо інформацію, необхідну для його скасування: приєднаний корінь, попередній розмір компоненти та її попередні вартості.

Після завершення рекурсивного виклику скасуємо всі об'єднання, виконані після збереженого стану, а також відновимо попередню сумарну вартість і стан суперечливості.

Якщо в якийсь момент обмеження стали суперечливими, відповіді для всіх кольорів поточного відрізка дорівнюють $- 1$ .

Справді, усі ребра, які вже враховані в DSU, повинні залишатися в графі для кожного кольору цього відрізка. Тому видалення будь-якого з цих кольорів не зможе усунути суперечність.

Отже, можемо одразу записати $- 1$ для всього відрізка, не виконуючи подальших рекурсивних викликів.

Коли дійдемо до листка, що відповідає кольору $c$ , відповідь дорівнюватиме

an s_{c} = {- 1, c u r, якщо обмеження суперечливі, інакше .

ans_c= \begin{cases} -1, & \text{якщо обмеження суперечливі},\\ cur, & \text{інакше}. \end{cases}

Такий підхід також правильно обробляє кратні ребра, петлі та кольори, які взагалі не зустрічаються серед ребер.

Асимптотика

Глибина рекурсії методу розділяй і володарюй становить $O (lo g k)$ O(\log k).

Кожне ребро обробляється не більше одного разу на кожному рівні рекурсії, тому сумарно виконується $O (m lo g k)$ O(m\log k) операцій DSU.

Оскільки ми використовуємо об'єднання за розміром без стиснення шляхів, пошук кореня працює за $O (lo g n)$ O(\log n).

Отже, загальна часова складність становить

O (n + (m lo g n + k) lo g k) .

O(n+(m\log n+k)\log k).

Для зберігання DSU, історії відкатів та ребер потрібно $O (n + m + k)$ O(n+m+k) пам'яті.

Оскільки сумарна вартість може досягати $2 \cdot 1 0^{14}$ 2\cdot 10^{14}, необхідно використовувати 64-бітний цілочисельний тип.

Реалізація

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

struct Edge {
    int u, v, b;
};

struct Change {
    int u, v, sz;
    ll c0, c1;
};

int n, m, k;
int p[N], sz[N], xr[N];
ll cost[N][2], ans[N], cur;
int bad;

vector<Edge> edges[N];
vector<Change> hist;

pair<int, int> get(int v) {
    int x = 0;

    while (v != p[v]) {
        x ^= xr[v];
        v = p[v];
    }

    return {v, x};
}

void join(Edge e) {
    if (bad) return;

    auto [u, x] = get(e.u);
    auto [v, y] = get(e.v);

    int d = x ^ y ^ e.b;

    if (u == v) {
        if (d) bad = 1;
        return;
    }

    if (sz[u] < sz[v]) swap(u, v);

    hist.push_back({u, v, sz[u], cost[u][0], cost[u][1]});

    cur -= min(cost[u][0], cost[u][1]);
    cur -= min(cost[v][0], cost[v][1]);

    p[v] = u;
    xr[v] = d;
    sz[u] += sz[v];

    cost[u][0] += cost[v][d];
    cost[u][1] += cost[v][d ^ 1];

    cur += min(cost[u][0], cost[u][1]);
}

void rollback(int t, ll old, int old_bad) {
    while ((int)hist.size() > t) {
        auto ch = hist.back();
        hist.pop_back();

        p[ch.v] = ch.v;
        xr[ch.v] = 0;

        sz[ch.u] = ch.sz;
        cost[ch.u][0] = ch.c0;
        cost[ch.u][1] = ch.c1;
    }

    cur = old;
    bad = old_bad;
}

void dfs(int l, int r) {
    if (bad) {
        for (int i = l; i <= r; i++) {
            ans[i] = -1;
        }
        return;
    }

    if (l == r) {
        ans[l] = cur;
        return;
    }

    int mid = (l + r) / 2;

    int t = hist.size();
    ll old = cur;
    int old_bad = bad;

    for (int i = mid + 1; i <= r; i++) {
        for (auto e : edges[i]) {
            join(e);
        }
    }

    dfs(l, mid);
    rollback(t, old, old_bad);

    for (int i = l; i <= mid; i++) {
        for (auto e : edges[i]) {
            join(e);
        }
    }

    dfs(mid + 1, r);
    rollback(t, old, old_bad);
}

void solve() {
    cin >> n >> m >> k;

    string a;
    cin >> a;

    for (int i = 1; i <= n; i++) {
        ll w;
        cin >> w;

        p[i] = i;
        sz[i] = 1;

        cost[i][0] = (a[i - 1] == '1' ? w : 0);
        cost[i][1] = (a[i - 1] == '0' ? w : 0);
    }

    for (int i = 0; i < m; i++) {
        int u, v, b, c;
        cin >> u >> v >> b >> c;

        edges[c].push_back({u, v, b});
    }

    dfs(1, k);

    for (int i = 1; i <= k; i++) {
        cout << ans[i] << (i == k ? '\n' : ' ');
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

C++