Submission #3890374


Source Code Expand

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

struct UnionFind
{
    void init(int n)
    {
        mN = n;
        mNodeTbl.resize(mN);
        mRankTbl.resize(mN);
        REP(i, mN)
        {
            mNodeTbl[i] = i;
            mRankTbl[i] = 0;
        }
    }
    int find(int x)
    {
        if (x == mNodeTbl[x])
            return x;
        return mNodeTbl[x] = find(mNodeTbl[x]);
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    void unit(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (mRankTbl[x] < mRankTbl[y])
        {
            mNodeTbl[x] = y;
        }
        else
        {
            mNodeTbl[y] = x;
            if (mRankTbl[x] == mRankTbl[y])
                mRankTbl[x]++;
        }
    }

    int mN;
    vector<int> mNodeTbl;
    vector<int> mRankTbl;
};

struct Node
{
    int a;
    int b;
    int c;
};

ll M[105][105];
Node n[100005];
int x[2] = {0, 1}, y[2] = {1, 0};

int main()
{
    int H, W;
    cin >> H >> W;
    pll S, G;
    cin >> S.first >> S.second >> G.first >> G.second;
    ll cost = 0;
    REP(i, H)
    {
        REP(j, W)
        {
            cin >> M[i][j];
            cost += M[i][j];
        }
    }

    int num = 0;
    REP(h, H)
    {
        REP(w, W)
        {
            REP(i, 2)
            {
                int nh = h + y[i], nw = w + x[i];
                if (nh >= H || nw >= W)
                    continue;
                Node node;
                node.a = W * h + w;
                node.b = W * nh + nw;
                node.c = M[h][w] * M[nh][nw];
                n[num++] = node;
            }
        }
    }
    UnionFind uf;
    uf.init(H * W);
    sort(n, n + num, [](Node a, Node b) { return a.c > b.c; });

    REP(i, num)
    {
        if (uf.same(n[i].a, n[i].b))
            continue;
        uf.unit(n[i].a, n[i].b);
        cost += n[i].c;
    }
    cout << cost << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Game on a Grid
User coco18000
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2331 Byte
Status AC
Exec Time 5 ms
Memory 640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 32
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 5 ms 640 KB
subtask1_08.txt AC 5 ms 640 KB
subtask1_09.txt AC 5 ms 640 KB
subtask1_10.txt AC 5 ms 640 KB
subtask1_11.txt AC 5 ms 640 KB
subtask1_12.txt AC 5 ms 640 KB
subtask1_13.txt AC 5 ms 640 KB
subtask1_14.txt AC 5 ms 640 KB
subtask1_15.txt AC 5 ms 640 KB
subtask1_16.txt AC 4 ms 640 KB
subtask1_17.txt AC 1 ms 384 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 384 KB
subtask1_20.txt AC 4 ms 640 KB
subtask1_21.txt AC 4 ms 640 KB
subtask1_22.txt AC 4 ms 640 KB
subtask1_23.txt AC 4 ms 640 KB
subtask1_24.txt AC 1 ms 256 KB
subtask1_25.txt AC 1 ms 256 KB
subtask1_26.txt AC 1 ms 256 KB
subtask1_27.txt AC 1 ms 256 KB
subtask1_28.txt AC 1 ms 256 KB
subtask1_29.txt AC 1 ms 256 KB