제출 #1232200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232200		alterio	축구 경기장 (IOI23_soccer)	C++20	12 / 100	4594 ms	35620 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2010;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int ldr[mxn * mxn], rnk[mxn * mxn];
int N;

int F(int x, int y) {
    return x * N + y;
}

int Find(int x) {
    if (ldr[x] == x) return x;
    return ldr[x] = Find(ldr[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (rnk[y] > rnk[x]) swap(x, y);
    ldr[y] = x;
    rnk[x] += rnk[y];
}

int biggest_stadium(int _N, vector<vector<int>> V) {
    N = _N;

    
    auto valid = [&] (int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    };

    int SZ = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (V[i][j]) continue;
            SZ++;
            queue<pair<int, int>> q;
            q.push({i, j});
            bool visited[N][N];
            memset(visited, 0, sizeof(visited));
            visited[i][j] = 1;
            queue<pair<int, int>> newQ;
            while (q.size()) {
                auto fr = q.front();
                q.pop();
                for (int d = 0; d < 4; d++) {
                    for (int mult = 1; mult < N; mult++) {
                        int nx = fr.first + dx[d] * mult, ny = fr.second + dy[d] * mult;
                        if (!valid(nx, ny) || V[nx][ny]) break;
                        if (visited[nx][ny]) continue;
                        visited[nx][ny] = 1;
                        newQ.push({nx, ny});
                    }
                }
            }
            while (newQ.size()) {
                auto fr = newQ.front();
                newQ.pop();
                for (int d = 0; d < 4; d++) {
                    for (int mult = 1; mult < N; mult++) {
                        int nx = fr.first + dx[d] * mult, ny = fr.second + dy[d] * mult;
                        if (!valid(nx, ny) || V[nx][ny]) break;
                        if (visited[nx][ny]) continue;
                        visited[nx][ny] = 1;
                    }
                }
            }
            for (int l = 0; l < N; l++) {
                for (int w = 0; w < N; w++) {
                    if (!V[l][w] && !visited[l][w]) return 0;
                }
            }
        }
    }
    return SZ;

    // for (int i = 0; i < N * N; i++) ldr[i] = i, rnk[i] = 1;
    // int highest[N], lowest[N];
    // for (int i = 0; i < N; i++) highest[i] = N + 1, lowest[i] = -1;
    
    // auto valid = [&] (int x, int y) {
    //     return x >= 0 && x < N && y >= 0 && y < N;
    // };

    // int SZ = 0;

    // for (int i = 0; i < N; i++) {
    //     for (int j = 0; j < N; j++) {
    //         if (V[i][j]) continue;
    //         SZ++;
    //         for (int d = 0; d < 4; d++) {
    //             int nx = i + dx[d], ny = j + dy[d];
    //             if (!valid(nx, ny) || V[nx][ny]) continue;
    //             Union(F(i, j), F(nx, ny));
    //         }
    //     }
    // }
    // set<int> s;
    // for (int i = 0; i < N; i++) {
    //     for (int j = 0; j < N; j++) {
    //         if (V[i][j]) continue;
    //         s.insert(Find(F(i, j)));
    //     }
    // }
    // if (s.size() > 1 || !s.size()) return 0;
    // for (int j = 0; j < N; j++) {
    //     bool flag = 0, obst = 0;
    //     for (int i = 0; i < N; i++) {
    //         if (V[i][j]) {
    //             if (flag) obst = 1;
    //             continue;
    //         }
    //         if (obst) return 0;
    //         highest[j] = min(highest[j], i);
    //         lowest[j] = max(lowest[j], i);
    //         flag = 1;
    //     }
    // } 
    // for (int j = 0; j < N; j++) {
    //     if (highest[j] == N + 1) continue;
    //     pair<int, int> p = {highest[j], lowest[j]};
    //     j++;
    //     while (j < N && p == make_pair(highest[j], lowest[j])) j++;
    //     if (j == N || highest[j] == N + 1) return SZ;
    //     pair<int, int> newP = {highest[j], lowest[j]};
    //     if (newP.first != p.first && newP.second != p.second) return 0;
    //     j++;
    //     while (j < N && newP == make_pair(highest[j], lowest[j])) j++;
    //     if (j == N || highest[j] == N + 1) return SZ;
    //     return 0;
    // }
}

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