logoChat01.ai

Задано подвешенное дерево, содержащее n вершин, ...

Creato il: 24 dicembre 2025

Risposto usando GPT-5.2 da Chat01

Domanda

Задано подвешенное дерево, содержащее
n
вершин, пронумерованных от 0 до
n
−
1
. Требуется ответить на
m
запросов о наименьшем общем предке для пары вершин.

Запросы генерируются следующим образом. Заданы числа
a
1
,
a
2
и числа
x
,
y
и
z
.

Числа
a
3
,
…
,
a
2
m
генерируются следующим образом:
a
i

(
x
⋅
a
i
−
2
+
y
⋅
a
i
−
1
+
z
)
mod
n
. Первый запрос имеет вид
⟨
a
1
,
a
2
⟩
.
i
-й запрос имеет вид
⟨
a
2
i
−
1
,
a
2
i
⟩
.

Формат входных данных
Первая строка содержит два числа:
n
(
1
≤
n
≤
1
000
000
) и
m
(
1
≤
m
≤
1
000
000
). Корень дерева имеет номер 0. Вторая строка содержит
n
−
1
целых чисел,
i
-е из этих чисел задает номер родителя вершины
i
.

Третья строка содержит целые числа
a
1
и
a
2
(
0
≤
a
i
≤
n
−
1
).

Четвёртая строка содержит три целых числа:
x
,
y
и
z
(
0
≤
x
,
y
,
z
≤
10
9
)

Формат выходных данных
Выведите в выходной файл сумму номеров вершин — ответов на все запросы.
как уменьшить расход памяти в коде
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
using ull = unsigned long long;
using ll = long long;
using ld = long double;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using min_queue = priority_queue<T, vector<T>, greater<T> >;

const int N = 1e6 + 5;
const int K = 20;

vector<pair<int, int> >qq[N];
vector<int>g[N];
int used[N], usedqq[N], p[N], lead[N];
int n, m;
ll ans = 0;

int get(int x) {
return (x == p[x] ? x : p[x] = get(p[x]));
}

void comb(int u, int v, int nlead) {
u = get(u); v = get(v);
p[u] = v;
lead[v] = nlead;
}

void dfs(int u) {
used[u] = true;
for (int v : g[u]) {
if (!used[v]) {
dfs(v);
comb(u, v, u);
}
}
for (auto [v, i] : qq[u]) {
if (!usedqq[i] && used[v]) {
// cout << u << ' ' << v << ' ' << lead[get(v)] << '\n';
usedqq[i] = true;
ans += lead[get(v)];
}
}
}

void solve() {
cin >> n >> m;
for (int i = 1; i < n; i++) {
int p;
cin >> p;
g[p].push_back(i);
g[i].push_back(p);
}
int u, v, x, y, z;
cin >> u >> v >> x >> y >> z;
for (int i = 1; i <= m; i++) {
qq[u].push_back({v, i});
qq[v].push_back({u, i});
int nu, nv;
nu = (1ll * u * x + 1ll * v * y + z) % n;
nv = (1ll * v * x + 1ll * nu * y + z) % n;
u = nu; v = nv;
}
for (int i = 0; i < n; i++) {
p[i] = i;
lead[i] = i;
}
dfs(0);
cout << ans;
}

int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
srand(time(0));
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
solve();
return 0;
}

Pensiero

Thought for 6s

Risposta

У вас «съедает» память не DSU и не used[], а vector<...> g[N] и vector<...> qq[N].
При N = 1e6 вы создаёте миллион объектов vector два раза. Даже пустой vector занимает ~24 байта (зависит от STL), т.е. только на «обёртки» это десятки мегабайт на каждый массив, плюс фрагментация и ёмкости. Поэтому и не влезает.

Ниже — что делать, чтобы уложиться по памяти.

1) Не хранить дерево как vector<int> g[N]

Ввод уже даёт родителя вершины i → значит можно хранить только список детей (направленное дерево), без обратных рёбер.

Самый компактный вариант — “forward-star” (как в Си):

cpp
// для детей
vector<int> head(n, -1);
vector<int> to(n-1);
vector<int> nxt(n-1);
int ec = 0;

auto add_edge = [&](int parent, int child){
    to[ec] = child;
    nxt[ec] = head[parent];
    head[parent] = ec++;
};

Память: head (n int) + to,nxt (2*(n-1) int) ≈ ~12 МБ при int32.

2) Запросы тоже не хранить как vector<pair<int,int>> qq[N]

Аналогично, храните все “половинки запросов” в плоских массивах размера 2m:

cpp
vector<int> qhead(n, -1);
vector<int> qto(2*m);
vector<int> qid(2*m);
vector<int> qnxt(2*m);
int qc = 0;

auto add_query = [&](int u, int v, int id){
    qto[qc] = v; qid[qc] = id; qnxt[qc] = qhead[u]; qhead[u] = qc++;
};

И добавляете в обе стороны: add_query(u,v,i); add_query(v,u,i);

Это убирает миллион vector и убирает pair (ещё накладные расходы).

3) used[] и usedqq[] сделать байтовыми (или битовыми)

  • int used[N] → 4 МБ на массив.
  • Лучше vector<uint8_t> или vector<char>: 1 МБ.
  • Ещё лучше битсет (вручную) — ~125 КБ на 1e6, но обычно uint8_t уже достаточно.
cpp
vector<uint8_t> used(n, 0);
vector<uint8_t> answered(m+1, 0); // вместо usedqq[]

4) Убрать рекурсию dfs (стек переполнится на 1e6)

Даже если память починить, dfs(0) рекурсией почти наверняка упадёт.
Нужен итеративный обход с фазами “вошли/вышли”, чтобы корректно делать comb(u, child, u) после обработки ребёнка.

Схема стека:

cpp
struct Frame { int u; int e; }; // e = текущий edge-индекс в списке детей
stack<Frame> st;
st.push({0, head[0]});
used[0]=1;

while(!st.empty()){
    auto &f = st.top();
    int u = f.u;
    if(f.e != -1){
        int idEdge = f.e;
        f.e = nxt[idEdge];
        int v = to[idEdge];
        used[v]=1;
        st.push({v, head[v]});
    } else {
        // "выход" из u: обработать запросы у u
        for(int qi = qhead[u]; qi != -1; qi = qnxt[qi]){
            int v = qto[qi], id = qid[qi];
            if(!answered[id] && used[v]){
                answered[id]=1;
                ans += lead[ get(v) ];
            }
        }
        st.pop();
        if(!st.empty()){
            int parent = st.top().u;
            comb(parent, u, parent); // как в Tarjan: после возврата из child
        }
    }
}

5) DSU: итеративный get (не обязательно, но можно)

Чтобы не было рекурсивной глубины в get(), можно сделать с компрессией путей итеративно. Не критично, но приятно.

Итого: что вы выигрываете

Вы убираете главную дыру:

  • ❌ vector<int> g[N] + vector<pair<int,int>> qq[N] → огромные накладные расходы на миллион контейнеров
  • ✅ плоские массивы head/to/nxt и qhead/qto/qid/qnxt → предсказуемая память ~ (дерево 12 МБ) + (запросы ~ 24–32 МБ) + служебные массивы (ещё ~10 МБ)

В сумме обычно укладывается в типичные лимиты (64–256 МБ), в зависимости от точного лимита и реализации STL.

Если хотите — я могу прямо переписать ваш код целиком в этом стиле (без vector[N], без рекурсии), сохранив Tarjan LCA и генерацию запросов 1-в-1.

Domanda

да напиши код что бы заходил в ограничения 64 мб

Pensiero

Thought for 5s

Risposta

Ниже — полностью переписанный вариант в Tarjan LCA + DSU, который реально влезает в 64 МБ при n,m ≤ 1e6.

Ключевые идеи экономии памяти:

  • Никаких vector<...> g[N] и vector<...> qq[N] (миллионы vector → огромные накладные расходы).
  • Дерево храним как списки детей в массивах head/to/nxt (т.к. во входе дан родитель, обратные рёбра не нужны).
  • Запросы храним в массивах qhead/qto/qid/qnxt размером 2*m.
  • used и answered — uint8_t, а не int.
  • DFS итеративный (рекурсия на 1e6 вершин упадёт по стеку).

По памяти (приблизительно):

  • дерево: ~12 МБ
  • запросы: ~24 МБ
  • DSU + lead: ~8 МБ
  • used + answered: ~2 МБ
  • стек обхода: ~8 МБ
    Итого ~54 МБ (обычно проходит в 64 МБ).

✅ Код (64 МБ)

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

using ll = long long;

// ---------- Fast Input ----------
struct FastInput {
    static const int BUFSIZE = 1 << 20;
    int idx, size;
    char buf[BUFSIZE];

    FastInput() : idx(0), size(0) {}

    inline char read() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    template<class T>
    bool readInt(T &out) {
        char c;
        do {
            c = read();
            if (!c) return false;
        } while (c <= ' ');

        bool neg = false;
        if (c == '-') {
            neg = true;
            c = read();
        }

        T val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        out = neg ? -val : val;
        return true;
    }
};

// ---------- DSU (iterative find with compression) ----------
static inline int dsu_find(int x, int *p) {
    int root = x;
    while (p[root] != root) root = p[root];
    while (p[x] != x) {
        int nx = p[x];
        p[x] = root;
        x = nx;
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    FastInput in;

    int n, m;
    if (!in.readInt(n)) return 0;
    in.readInt(m);

    // ---------- Tree: children adjacency (head/to/nxt) ----------
    // edges count = n-1
    vector<int> head(n, -1);
    vector<int> to(max(0, n - 1));
    vector<int> nxt(max(0, n - 1));
    int ec = 0;

    auto add_child = [&](int parent, int child) {
        to[ec] = child;
        nxt[ec] = head[parent];
        head[parent] = ec++;
    };

    for (int i = 1; i < n; i++) {
        int par;
        in.readInt(par);
        add_child(par, i);
    }

    // ---------- Queries adjacency (qhead/qto/qid/qnxt) ----------
    // store both directions => 2*m
    vector<int> qhead(n, -1);
    vector<int> qto(2LL * m);
    vector<int> qid(2LL * m);
    vector<int> qnxt(2LL * m);
    int qc = 0;

    auto add_query = [&](int u, int v, int id) {
        qto[qc] = v;
        qid[qc] = id;
        qnxt[qc] = qhead[u];
        qhead[u] = qc++;
    };

    int a1, a2;
    in.readInt(a1);
    in.readInt(a2);

    int x, y, z;
    in.readInt(x);
    in.readInt(y);
    in.readInt(z);

    int u = a1, v = a2;
    for (int i = 1; i <= m; i++) {
        add_query(u, v, i);
        add_query(v, u, i);

        long long nu = (1LL * x * u + 1LL * y * v + z) % n;
        long long nv = (1LL * x * v + 1LL * y * (int)nu + z) % n;
        u = (int)nu;
        v = (int)nv;
    }

    // ---------- DSU arrays ----------
    vector<int> p(n);
    vector<int> lead(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        lead[i] = i;
    }

    // ---------- used / answered (1 byte each) ----------
    vector<uint8_t> used(n, 0);
    vector<uint8_t> answered(m + 1, 0);

    // ---------- Iterative DFS for Tarjan LCA ----------
    // Frame: current vertex and current edge iterator (index in adjacency list)
    struct Frame { int u; int e; };
    vector<Frame> st;
    st.reserve(n);

    ll ans = 0;

    // start from root 0
    used[0] = 1;
    st.push_back({0, head[0]});

    while (!st.empty()) {
        Frame &f = st.back();
        int cur = f.u;

        if (f.e != -1) {
            // go deeper to next child
            int eidx = f.e;
            f.e = nxt[eidx];
            int child = to[eidx];

            used[child] = 1;
            st.push_back({child, head[child]});
        } else {
            // exit vertex: answer all queries for this vertex
            for (int qi = qhead[cur]; qi != -1; qi = qnxt[qi]) {
                int other = qto[qi];
                int id = qid[qi];
                if (!answered[id] && used[other]) {
                    answered[id] = 1;
                    int r = dsu_find(other, p.data());
                    ans += lead[r];
                }
            }

            // pop and union with parent (Tarjan: after child processed)
            st.pop_back();
            if (!st.empty()) {
                int parent = st.back().u;
                int ru = dsu_find(parent, p.data());
                int rv = dsu_find(cur, p.data());
                // union ru into rv (same as your comb(u,v,u) but в нужном месте)
                p[ru] = rv;
                lead[rv] = parent;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

Почему именно так влезает в 64 МБ

Самое важное: мы убрали массивы из миллиона vector.
Один пустой vector ~24 байта → 1e6 * 24 ≈ 24 МБ только за обёртки, и у вас их было два массива (g и qq) → уже ~48 МБ, ещё до данных.

Если хочешь — могу:

  • сделать ещё компактнее (битовые used/answered → минус ~1.8 МБ),
  • или ускорить генерацию/обработку (оптимизация DSU + IO) без увеличения памяти.

Condividi questa Q&A