oj.uz

Submission #944384

# Submission time Handle Problem Language Result Execution time Memory
944384 2024-03-12T16:23:07 Z Nhoksocqt1 Soccer Stadium (IOI23_soccer) C++17
12 / 100
 4500 ms 39160 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 2003;
const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};

struct State {
    int x, y, t;

    State(int _x = 0, int _y = 0, int _t = 0) : x(_x), y(_y), t(_t) {};
};

int dp[MAXN][MAXN][4], nSize;
bool dx[MAXN][MAXN][4], isTree[MAXN][MAXN];

bool bfsCheck(int x, int y) {
    int cntEmpty(0);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            for (int t = 0; t < 4; ++t) {
                dp[i][j][t] = (isTree[i][j]) ? -1 : 1e9;
                dx[i][j][t] = 0;
            }

            cntEmpty += (!isTree[i][j]);
        }
    }

    deque<State> dq;
    for (int t = 0; t < 4; ++t) {
        dq.push_back(State(x, y, t));
        dp[x][y][t] = 1;
    }

    int maxdp(0), cnt(0);
    while(sz(dq)) {
        int x(dq.front().x), y(dq.front().y), t(dq.front().t);
        dq.pop_front();

        if(dx[x][y][t])
            continue;

        dx[x][y][t] = 1;
        for (int id = 0; id < 4; ++id) {
            int u(x + lx[id]), v(y + ly[id]);
            if(min(u, v) < 1 || max(u, v) > nSize || dp[u][v][id] <= dp[x][y][t] + (t != id))
                continue;

            dp[u][v][id] = dp[x][y][t] + (t != id);
            if(t == id) {
                dq.push_front(State(u, v, id));
            } else {
                dq.push_back(State(u, v, id));
            }
        }
    }

    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            int mindp = min({dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]});
            maxdp = max(maxdp, mindp);
            cnt += (!isTree[i][j] && mindp < int(1e9));
        }
    }

    return (maxdp <= 2 && cnt == cntEmpty);
}

int biggest_stadium(int n, vector<vector<int>> F) {
    nSize = n;

    int cntTree(0);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            isTree[i][j] = (F[i - 1][j - 1]);
            cntTree += isTree[i][j];
        }
    }

    bool check(1);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            if(isTree[i][j])
                continue;

            if(i == 1 || j == 1 || i == nSize || j == nSize || isTree[i - 1][j] || isTree[i][j - 1] || isTree[i][j + 1] || isTree[i + 1][j])
                check &= (bfsCheck(i, j));
        }
    }

    if(cntTree == 0 || check)
        return nSize * nSize - cntTree;

    return 1;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "soccer"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<vector<int>> F;
    int n;
    cin >> n;

    F.resize(n);
    for (int i = 0; i < n; ++i) {
        F[i].resize(n);
        for (int j = 0; j < n; ++j)
            cin >> F[i][j];
    }

    int ans = biggest_stadium(n, F);
    cout << "ANSWER: " << ans << '\n';

    return 0;
}

#endif // Nhoksocqt1

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 2 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Partially correct 1 ms 4444 KB partial
7 Partially correct 372 ms 13388 KB partial
8 Execution timed out 4525 ms 39160 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 2 ms 4444 KB ok
3 Partially correct 1 ms 4444 KB partial
4 Partially correct 1 ms 4444 KB partial
5 Partially correct 1 ms 4444 KB partial
6 Partially correct 1 ms 4444 KB partial
7 Partially correct 1 ms 4444 KB partial
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4444 KB ok
10 Partially correct 1 ms 4444 KB partial
11 Partially correct 2 ms 4440 KB partial
12 Partially correct 1 ms 4696 KB partial
13 Correct 1 ms 4444 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB partial
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Partially correct 1 ms 4444 KB partial
5 Partially correct 1 ms 4444 KB partial
6 Partially correct 1 ms 4444 KB partial
7 Partially correct 1 ms 4444 KB partial
8 Partially correct 1 ms 4444 KB partial
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Partially correct 1 ms 4444 KB partial
12 Partially correct 2 ms 4440 KB partial
13 Partially correct 1 ms 4696 KB partial
14 Correct 1 ms 4444 KB ok
15 Partially correct 1 ms 4444 KB partial
16 Partially correct 1 ms 4440 KB partial
17 Partially correct 1 ms 4444 KB partial
18 Partially correct 1 ms 4444 KB partial
19 Partially correct 1 ms 4444 KB partial
20 Correct 1 ms 4444 KB ok
21 Correct 1 ms 4444 KB ok
22 Partially correct 1 ms 4444 KB partial
23 Partially correct 1 ms 4548 KB partial
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4440 KB partial
26 Partially correct 1 ms 4444 KB partial

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB partial
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Partially correct 1 ms 4444 KB partial
7 Partially correct 1 ms 4444 KB partial
8 Partially correct 1 ms 4444 KB partial
9 Partially correct 1 ms 4444 KB partial
10 Partially correct 1 ms 4444 KB partial
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Partially correct 1 ms 4444 KB partial
14 Partially correct 2 ms 4440 KB partial
15 Partially correct 1 ms 4696 KB partial
16 Correct 1 ms 4444 KB ok
17 Partially correct 1 ms 4444 KB partial
18 Partially correct 1 ms 4440 KB partial
19 Partially correct 1 ms 4444 KB partial
20 Partially correct 1 ms 4444 KB partial
21 Partially correct 1 ms 4444 KB partial
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4444 KB ok
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4548 KB partial
26 Partially correct 1 ms 4444 KB partial
27 Partially correct 1 ms 4440 KB partial
28 Partially correct 1 ms 4444 KB partial
29 Partially correct 1 ms 4444 KB partial
30 Partially correct 28 ms 4620 KB partial
31 Partially correct 28 ms 4624 KB partial
32 Partially correct 3 ms 4440 KB partial
33 Partially correct 1 ms 4444 KB partial
34 Correct 2 ms 4444 KB ok
35 Correct 3 ms 4444 KB ok
36 Partially correct 2 ms 4440 KB partial
37 Partially correct 2 ms 4444 KB partial
38 Partially correct 2 ms 4444 KB partial
39 Partially correct 2 ms 4444 KB partial
40 Partially correct 5 ms 4444 KB partial
41 Partially correct 7 ms 4444 KB partial

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB partial
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Partially correct 1 ms 4444 KB partial
7 Partially correct 1 ms 4444 KB partial
8 Partially correct 1 ms 4444 KB partial
9 Partially correct 1 ms 4444 KB partial
10 Partially correct 1 ms 4444 KB partial
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Partially correct 1 ms 4444 KB partial
14 Partially correct 2 ms 4440 KB partial
15 Partially correct 1 ms 4696 KB partial
16 Correct 1 ms 4444 KB ok
17 Partially correct 1 ms 4444 KB partial
18 Partially correct 1 ms 4440 KB partial
19 Partially correct 1 ms 4444 KB partial
20 Partially correct 1 ms 4444 KB partial
21 Partially correct 1 ms 4444 KB partial
22 Correct 1 ms 4444 KB ok
23 Correct 1 ms 4444 KB ok
24 Partially correct 1 ms 4444 KB partial
25 Partially correct 1 ms 4548 KB partial
26 Partially correct 1 ms 4444 KB partial
27 Partially correct 1 ms 4440 KB partial
28 Partially correct 1 ms 4444 KB partial
29 Partially correct 1 ms 4444 KB partial
30 Partially correct 28 ms 4620 KB partial
31 Partially correct 28 ms 4624 KB partial
32 Partially correct 3 ms 4440 KB partial
33 Partially correct 1 ms 4444 KB partial
34 Correct 2 ms 4444 KB ok
35 Correct 3 ms 4444 KB ok
36 Partially correct 2 ms 4440 KB partial
37 Partially correct 2 ms 4444 KB partial
38 Partially correct 2 ms 4444 KB partial
39 Partially correct 2 ms 4444 KB partial
40 Partially correct 5 ms 4444 KB partial
41 Partially correct 7 ms 4444 KB partial
42 Execution timed out 4559 ms 30684 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB partial
2 Correct 1 ms 4444 KB ok
3 Correct 2 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 4444 KB ok
7 Partially correct 1 ms 4444 KB partial
8 Partially correct 372 ms 13388 KB partial
9 Execution timed out 4525 ms 39160 KB Time limit exceeded
10 Halted 0 ms 0 KB -