Submission #542774

#	Time	Username	Problem	Language	Result	Execution time	Memory
542774		Olympia	Domino (COCI15_domino)	C++17	10 / 160	1966 ms	391492 KiB

domino

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

using namespace std;
class Edge {
public:
    pair<int,int> from;
    pair<int,int> to;
    int weight;
    bool operator < (Edge e2) const {
        return (e2.weight < weight);
    }
};
int K;
class DisjointSetUnion {
public:
    vector<int> parent;
    vector<int> compSize;
    DisjointSetUnion (int N) {
        parent.resize(N), compSize.assign(N, 1);
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }
    int find_head (int x) {
        if (x == parent[x]) return x;
        return find_head(parent[x]);
    }
    pair<bool,int> join (int x, int y) {
        x = find_head(x), y = find_head(y);
        if (x == y) return {false, -1};
        if (compSize[x] > compSize[y]) swap(x, y);
        compSize[y] += compSize[x];
        parent[x] = y;
        if (compSize[y] >= 2 * K) {
            return {true, y};
        } else {
            return {false, -1};
        }
        //return {true, compSize[y] >= 2 * K};
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N >> K;
    DisjointSetUnion dsu(N * N);
    vector<vector<int>> arr(N);
    vector<Edge> edges;
    int64_t tot = 0;
    for (int i = 0; i < N; i++) {
        arr[i].resize(N);
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            tot += arr[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (abs(dx) == abs(dy)) continue;
                    if (i + dx < 0 || i + dx == N || j + dy < 0 || j + dy == N) continue;
                    edges.push_back({make_pair(i, j), make_pair(i + dx, j + dy), arr[i][j] + arr[i + dx][j + dy]});
                }
            }
        }
    }
    sort(edges.begin(), edges.end());
    int64_t cntr = 0;
    for (auto& e: edges) {
        pair<bool,int> p = dsu.join(e.from.first * N + e.from.second,  N * e.to.first + e.to.second);
        if (p.first) {
            for (int i = 0; i < N * N; i++) {
                if (dsu.find_head(i) == p.second) {
                    cntr += arr[i/N][i % N];
                }
            }
            cout << tot - cntr;
            break;
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10