Submission #839788

#	Time	Username	Problem	Language	Result	Execution time	Memory
839788		model_code	Soccer Stadium (IOI23_soccer)	C++17	18 / 100	4565 ms	12172 KiB

soccer

// time_limit/iterative_closure_random.cpp

#include "soccer.h"
#include <iostream>
int n;
std::vector<std::vector<int>> c;
std::vector<std::vector<int>> pre;
std::vector<std::vector<int>> st;

int sum(int a, int b, int x, int y)
{
    if (a > x)
        std::swap(a, x);
    if (b > y)
        std::swap(b, y);
    return pre[x][y] - (b ? pre[x][b - 1] : 0) - (a ? pre[a - 1][y] : 0) + (a && b ? pre[a - 1][b - 1] : 0);
}

bool connected(int a, int b, int x, int y)
{
    return sum(a, b, x, b) + sum(x, b, x, y) == 0 || sum(a, b, a, y) + sum(a, y, x, y) == 0;
}

std::vector<std::pair<int, int>> curr;
std::vector<std::pair<int, int>> vis;
int mx = 0;
void dfs(int x, int y)
{
    if (c[x][y] || st[x][y])
        return;
    vis.push_back({x, y});
    st[x][y] = 1;
    bool ok = true;
    for (auto i : curr)
    {
        ok &= connected(i.first, i.second, x, y);
    }

    if (ok)
    {
        curr.push_back({x, y});
    }
    else
    {
        return;
    }

    mx = std::max(mx, (int)curr.size());

    if (x > 0)
        dfs(x - 1, y);
    if (y > 0)
        dfs(x, y - 1);
    if (y + 1 < n)
        dfs(x, y + 1);
    if (x + 1 < n)
        dfs(x + 1, y);
}

int biggest_stadium(int N, std::vector<std::vector<int>> C)
{
    n = N;
    c = C;
    pre.assign(n, std::vector<int>(n, 0));
    st.assign(n, std::vector<int>(n, 0));
    std::vector<std::pair<int, int>> lst;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!c[i][j])
            {
                lst.push_back({i, j});
            }

            pre[i][j] = c[i][j];
            if (i)
                pre[i][j] += pre[i - 1][j];
            if (j)
                pre[i][j] += pre[i][j - 1];
            if (i && j)
                pre[i][j] -= pre[i - 1][j - 1];
        }
    }

    double start = clock();
    while (double(clock() - start) / CLOCKS_PER_SEC < 3.0)
    {
        std::pair<int, int> elem = lst[rand() % lst.size()];
        curr.clear();
        vis.clear();
        dfs(elem.first, elem.second);
        for (auto [x, y] : vis)
        {
            st[x][y] = 0;
        }
    }

    return mx;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30