oj.uz

Submission #839782

# Submission time Handle Problem Language Result Execution time Memory
839782 2023-08-30T15:51:12 Z model_code Soccer Stadium (IOI23_soccer) C++17
0 / 100
 41 ms 80756 KB 
// incorrect/largest_empty.cpp

#include "soccer.h"
#include <iostream>
#include <vector>
#include <set>
struct dsu
{
    std::vector<int> par;
    std::vector<int> sz;
    dsu(int n) : par(n, -1) { sz.assign(n, 1); }

    int get(int x)
    {
        if (par[x] == -1)
            return x;
        return par[x] = get(par[x]);
    }

    void merge(int x, int y)
    {
        int px = get(x), py = get(y);
        if (px == py)
            return;

        if (sz[px] > sz[py])
        {
            std::swap(px, py);
            std::swap(x, y); //:) lyft
        }

        sz[py] += sz[px];
        par[px] = py;
    }
};
const int MAXN = 3202;
int d0[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
dsu d(MAXN *MAXN);
int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
    int ans = 0;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (C[i][j] == 0)
            {
                for (int k = 0; k < 4; ++k)
                {
                    int ni = i + d0[k][0], nj = j + d0[k][1];
                    if (ni >= 0 && nj >= 0 && ni < N && nj < N)
                    {
                        if (0 == C[ni][nj])
                        {
                            d.merge(i * N + j, ni * N + nj);
                            ans = std::max(ans, d.sz[d.get(i * N + j)]);
                        }
                    }
                }
            }
        }
    }

    std::set<int> st;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int dd = d.get(i * N + j);
            if (d.sz[dd] == ans)
                st.insert(dd);
        }
    }

    std::cerr << st.size() << "\n";

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 80756 KB wrong
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80544 KB ok
2 Correct 39 ms 80544 KB ok
3 Correct 37 ms 80540 KB ok
4 Correct 33 ms 80548 KB ok
5 Incorrect 37 ms 80552 KB wrong
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 80544 KB ok
2 Correct 39 ms 80544 KB ok
3 Incorrect 38 ms 80532 KB wrong
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 80756 KB wrong
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 80756 KB wrong
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 80756 KB wrong
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 80756 KB wrong
2 Halted 0 ms 0 KB -