Submission #1213858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213858		trimkus	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	0 ms	324 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    vector<vector<bool>> vis(N, vector<bool>(N));
    int cnt = 0, res = 0;
    auto dfs = [&](auto& dfs, int i, int j) -> void {
        vis[i][j] = 1;
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (max(ni, nj) >= N || min(ni, nj) < 0 || vis[ni][nj] || F[ni][nj] == 1) continue;
            dfs(dfs, ni, nj);
        }
    };
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!vis[i][j] && F[i][j] == 0) {
                dfs(dfs, i, j);
                cnt += 1;
            }
            res += (F[i][j] == 0);
        }
    }
    if (cnt > 1) return 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (F[i][j] == 1) {
                if (i + 1 < N && i - 1 >= 0) {
                    if (F[i + 1][j] + F[i - 1][j] == 0) return 0;
                }
                if (j + 1 < N && j - 1 >= 0) {
                    if (F[i][j - 1] + F[i][j + 1] == 0) return 0;
                }
            }
        }
    }
    vector<array<int, 2>> pool;
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (F[i][j] == 0) {
                pool.push_back({i, j});
            }
        }
    }
    mt19937 rng(0);
    for (int it = 0; it < 10; ++it) {
        deque<array<int, 3>> dq;
        int idx = rng() % pool.size();
        int nowi = pool[idx][0];
        int nowj = pool[idx][1];
        vector<vector<int>> changes(N, vector<int>(N, N * N));
        dq.push_back({nowi, nowj, -1});
        while (dq.size()) {
            int i = dq.front()[0];
            int j = dq.front()[1];
            int dir = dq.front()[2];
            dq.pop_front();
            if (dir == -1) {
                changes[i][j] = 0;
                for (int k = 0; k < 4; ++k) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (max(ni, nj) >= N || min(ni, nj) < 0 || changes[ni][nj] <= changes[i][j] + 1 || F[ni][nj] == 1) continue;
                    changes[ni][nj] = changes[i][j] + 1;
                    dq.push_back({ni, nj, k});
                }
            }
            for (int k = 0; k < 4; ++k) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                int add = (dir != k);
                if (max(ni, nj) >= N || min(ni, nj) < 0 || changes[ni][nj] <= changes[i][j] + add || F[ni][nj] == 1) continue;
                changes[ni][nj] = changes[i][j] + add;
                if (add == 1) dq.push_back({ni, nj, k});
                else dq.push_front({ni, nj, k});
            }
            // cerr << i << " " << j << " = " << changes[i][j] << "\n";
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                // if (F[i][j] == 1) cerr << "- ";
                // else cerr << changes[i][j] << " ";
                if (F[i][j] == 0 && changes[i][j] > 2) {
                    res = 0;
                }
            }
            // cerr << "\n";
        }
        // cerr << "\n";
    }
    return res;
}

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