HDU6184 莫名爆内存求助

题目总版

1234567890sjx @ 2024-11-26 22:35:29

rt,萌新真的不知道哪里有问题了/kel

bool beginmem;
pair<signed, signed> edge[N];
vector<pair<signed, signed>> z[100100];
signed deg[N], n, m, vis[N];
int buc[N];
inline int binom2(int x) {
    return x * (x - 1) / 2;
}
map<pair<signed, signed>, int> id;
int cycle_3() {
    fill(deg + 1, deg + n + 1, 0ll);
    for (int i = 1; i <= m; ++i) {
        int x = edge[i].first, y = edge[i].second;
        ++deg[x], ++deg[y];
        edge[i] = {x, y};
    }
    for (int i = 1; i <= n; ++i) z[i].clear();
    for (int i = 1; i <= m; ++i) {
        int x = edge[i].first, y = edge[i].second;
        if (deg[x] < deg[y] || deg[x] == deg[y] && x < y) z[x].eb(y, i);
        else z[y].eb(x, i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (auto &j : z[i]) vis[j.first] = 1;
        for (auto &j : z[i]) for (auto &k : z[j.first]) 
            if (vis[k.first]) ++cnt, ++buc[j.second], ++buc[k.second], ++buc[id[{i, k.first}]];
        for (auto &j : z[i]) vis[j.first] = 0;
    }
    for (int i = 1; i <= n; ++i) z[i].clear(), z[i].shrink_to_fit();
    return cnt;
}
void run() {
    while (scanf("%d%d", &n, &m) == 2) {
        id.clear();
        fill(buc + 1, buc + m + 1, 0ll);
        for (int i = 1; i <= m; ++i)
            edge[i].first = read(), edge[i].second = read(), id[{edge[i].first, edge[i].second}] = id[{edge[i].second, edge[i].first}] = i;
        cycle_3();
        int cnt = 0;
        for (int i = 1; i <= m; ++i) cnt += binom2(buc[i]);
        cout << cnt << '\n';
    }
}
bool endmem;

|