oj.uz

Submission #542774

# Submission time Handle Problem Language Result Execution time Memory
542774 2022-03-27T23:58:10 Z Olympia Domino (COCI15_domino) C++17
10 / 160
 1966 ms 391492 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 24888 KB Output is correct
2 Correct 81 ms 24848 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 820 KB Output is correct
2 Incorrect 2 ms 820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1898 ms 391080 KB Output is correct
2 Incorrect 1433 ms 391492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1156 ms 363896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 466 ms 98144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1919 ms 391044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1886 ms 391100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1966 ms 391112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 471 ms 98100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1942 ms 391060 KB Output isn't correct
2 Halted 0 ms 0 KB -