WA 85pts 求调
  • 板块P4971 断罪者
  • 楼主sintle
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/9 22:59
  • 上次更新2024/11/10 10:21:20
查看原帖
WA 85pts 求调
681591
sintle楼主2024/11/9 22:59

rt

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

const int N = 1000005;
int T , w , k , n , m , a[N] , l[N] , r[N] , dis[N] , fa[N];
bool vis[N];

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int merge(int x , int y)
{
    if(!x || !y)
    {
        return x + y;
    }
    if(a[x] < a[y] || a[x] == a[y] && x > y)
    {
        swap(x , y);
    }
    r[x] = merge(r[x] , y);
    if(dis[l[x]] < dis[r[x]])
    {
        swap(l[x] , r[x]);
    }
    fa[l[x]] = fa[r[x]] = fa[x] = x;
    dis[x] = dis[r[x]] + 1;
    return x;
}

void del(int x)
{
    int ll = l[x] , rr = r[x];
    fa[ll] = ll;
    fa[rr] = rr;
    l[x] = r[x] = dis[x] = 0;
    merge(merge(ll , rr) , find(x));
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T >> w >> k;
    while(T--)
    {
        cin >> n >> m;
        fa[0] = l[0] = r[0] = dis[0] = 0;
        memset(vis , 0 , sizeof(vis));
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> a[i];
            fa[i] = i;
            l[i] = r[i] = dis[i] = 0;
        }
        while(m--)
        {
            int op , x , y;
            cin >> op;
            if(op == 2)
            {
                cin >> x;
                a[x] = 0;
                del(x);
            }
            else if(op == 3)
            {
                cin >> x >> y;
                x = find(x);
                a[x] -= (a[x] > y ? y : a[x]);
                del(x);
            }
            else
            {
                cin >> x >> y;
                x = find(x);
                y = find(y);
                if(x != y)
                {
                    merge(x , y);
                }
            }
        }
        int sum = 0 , mx = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            int rt = find(i);
            if(!vis[rt])
            {
                vis[rt] = 1;
                mx = max(mx , a[rt]);
                sum += a[rt];
            }
        }
        if(w == 2)
        {
            sum -= mx;
        }
        if(w == 3)
        {
            sum += mx;
        }
        if(sum == 0)
        {
            cout << "Gensokyo 0" << endl;
        }
        else if(sum <= k)
        {
            cout << "Heaven " << sum << endl;
        }
        else
        {
            cout << "Hell " << sum << endl;
        }
    }
    system("pause");
    return 0;
}
2024/11/9 22:59
加载中...