萌新刚学OI求助,过不了subtask 1的7 3 18和2的22 25
查看原帖
萌新刚学OI求助,过不了subtask 1的7 3 18和2的22 25
576378
creation_hy楼主2022/12/18 23:37

define int long long/开大数组无果

加assert的代码没有RE

求大佬帮忙看看(

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2505;
const int M = 1e4 + 5;
int n, m, p, head[N], to[M << 1], nxt[M << 1], etot;
int mx[N][3];
bool vis[N], can[N][N]; // can: dis < k
ll ans, a[N];
inline void link(int u, int v)
{
    to[etot] = v;
    nxt[etot] = head[u];
    head[u] = etot++;
}
inline void dfs(int x, int dep, int top)
{
    if (dep > p)
        return;
    vis[x] = true;
    if (x != top)
    {
        can[top][x] = true;
        if (can[1][x])
            if (a[x] > a[mx[top][0]])
            {
                mx[top][2] = mx[top][1];
                mx[top][1] = mx[top][0];
                mx[top][0] = x;
            }
            else if (a[x] > a[mx[top][1]])
            {
                mx[top][2] = mx[top][1];
                mx[top][1] = x;
            }
            else if (a[x] > a[mx[top][2]])
                mx[top][2] = x;
    }
    for (int i = head[x]; ~i; i = nxt[i])
        if (!vis[to[i]])
            dfs(to[i], dep + 1, top);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(head, -1, sizeof(head));
    cin >> n >> m >> p;
    for (int i = 2; i <= n; i++)
        cin >> a[i];
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        link(u, v);
        link(v, u);
    }
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        dfs(i, -1, i);
    }
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= n; j++)
            if (can[i][j])
                for (int x = 0; x < 3; x++)
                    if (mx[i][x])
                        for (int y = 0; y < 3; y++)
                            if (mx[j][y])
                                if (i != mx[j][y] && mx[i][x] != j && mx[i][x] != mx[j][y])
                                    ans = max(ans, a[i] + a[j] + a[mx[i][x]] + a[mx[j][y]]);
    assert(ans != 0);
    cout << ans;
    return 0;
}
2022/12/18 23:37
加载中...