超内存编译错误求助
查看原帖
超内存编译错误求助
1128376
hh1812827楼主2024/11/21 00:19

怎么还能超内存编译错误的?我把代码发给ai,ai说不会超过16MB,甚至把N改成2e3都超内存

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

#define pb push_back
#define __lg(x) (int)log2(x)
#define ep emplace
#define x first
#define y second
#define lowbit(x) (x&(-x))
#define T_T 0
#define endl "\n"
#define Endl "\n"
#define ls u<<1
#define rs u<<1|1
#define i128 __int128
#define nmsl cout<<"输出:\t";//农贸税率
#define retrun return 
typedef long long ll;
typedef double db;
typedef ll LL;
typedef unsigned long long ull;
typedef pair<double, double>PDD;
//mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rng(time(0));
int T = 1;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int N = 20002, M = 60;
const ll mod = 1e9 + 7;

//#define int ll
#define double long double
typedef pair<ll, int> PII;
ll n, m, x, y, k;
ll a[N];
vector<int>g[N];
vector<ll>ve(M);
vector<vector<PII>>h(N, vector<PII>(M));
int depth[N];
int fa[N][15];
void bfs(int root)//传入根节点,预处理fa和depth数组
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int>q;
    q.push(root);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < g[t].size(); i++)
        {
            int j = g[t][i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 21; k++)fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)//倍增法
{
    if (depth[a] < depth[b])swap(a, b);
    for (int i = 14; i >= 0; i--)
        if (depth[fa[a][i]] >= depth[b])a = fa[a][i];
    if (a == b)return a;
    for (int i = 14; i >= 0; i--)
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}
int qmax()
{
    int res = 0;
    for (int i = M - 1; i >= 0; i--)
        if ((res ^ ve[i]) > res)res ^= ve[i];
    return res;
}
void dfs(int u, int fa, int d)
{
    for (int i = 0; i < M; i++)h[u][i] = h[fa][i];
    ll t = a[u];
    for (int i = M - 1; i >= 0; i--)
    {
        if (!(t & (1ll << i)))continue;
        if (!h[u][i].x)
        {
            h[u][i] = { t,d };
            break;
        }
        if (d > h[u][i].y)swap(h[u][i].x, t), h[u][i].y = d;
        t ^= h[u][i].x;
    }
    for (int i : g[u])
        if (i == fa)continue;
        else dfs(i, u, d + 1);
}
int ins(ll x)//插入一个数
{
    for (int i = M; ~i; i--)
        if (x & (1ll << i))//位运算别忘开ll
            if (!ve[i]) { ve[i] = x; return 1; }
            else x ^= ve[i];
    return 0;
}
void merge(vector<PII>& a, vector<PII>& b, int d)
{
    for (auto i : a)
        if (i.y >= d)ins(i.x);
    for (auto i : b)
        if (i.y >= d)ins(i.x);
}

void jiangly()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    dfs(1, 0, 1);
    bfs(1);
    for (int i = 0; i < m; i++)
    {
        int u, v; cin >> u >> v;
        int t = lca(u, v);
        for (int i = 0; i < M; i++)ve[i] = 0;
        merge(h[u], h[v], depth[t]);
        cout << qmax() << endl;
    }
}
/*
3 10
1 1 10
2 1 10
3 1 1
*/
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //cout << fixed << setprecision(12);
    //cin >> T;
    while (T--)jiangly();
    return 0;
}
2024/11/21 00:19
加载中...