oj.uz

Submission #839788

# Submission time Handle Problem Language Result Execution time Memory
839788 2023-08-30T15:51:28 Z model_code Soccer Stadium (IOI23_soccer) C++17
18 / 100
 4500 ms 12172 KB 
// 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 272 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3000 ms 272 KB ok
2 Correct 3001 ms 280 KB ok
3 Correct 3001 ms 292 KB ok
4 Correct 3001 ms 288 KB ok
5 Correct 3000 ms 272 KB ok
6 Correct 3001 ms 272 KB ok
7 Correct 3275 ms 1992 KB ok
8 Execution timed out 4551 ms 12172 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3000 ms 272 KB ok
2 Correct 3001 ms 280 KB ok
3 Correct 3001 ms 276 KB ok
4 Correct 3001 ms 276 KB ok
5 Correct 3001 ms 280 KB ok
6 Correct 3001 ms 280 KB ok
7 Correct 3001 ms 280 KB ok
8 Correct 3001 ms 276 KB ok
9 Correct 3001 ms 280 KB ok
10 Correct 3001 ms 280 KB ok
11 Correct 3001 ms 280 KB ok
12 Correct 3000 ms 280 KB ok
13 Correct 3001 ms 276 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 272 KB partial
2 Correct 3000 ms 272 KB ok
3 Correct 3001 ms 280 KB ok
4 Correct 3001 ms 276 KB ok
5 Correct 3001 ms 276 KB ok
6 Correct 3001 ms 280 KB ok
7 Correct 3001 ms 280 KB ok
8 Correct 3001 ms 280 KB ok
9 Correct 3001 ms 276 KB ok
10 Correct 3001 ms 280 KB ok
11 Correct 3001 ms 280 KB ok
12 Correct 3001 ms 280 KB ok
13 Correct 3000 ms 280 KB ok
14 Correct 3001 ms 276 KB ok
15 Correct 3001 ms 272 KB ok
16 Correct 3001 ms 280 KB ok
17 Correct 3000 ms 280 KB ok
18 Correct 3001 ms 272 KB ok
19 Correct 3001 ms 276 KB ok
20 Correct 3001 ms 276 KB ok
21 Correct 3001 ms 272 KB ok
22 Correct 3001 ms 276 KB ok
23 Correct 3001 ms 272 KB ok
24 Correct 3001 ms 272 KB ok
25 Correct 3001 ms 272 KB ok
26 Correct 3001 ms 272 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 272 KB partial
2 Correct 3000 ms 272 KB ok
3 Correct 3001 ms 280 KB ok
4 Correct 3001 ms 292 KB ok
5 Correct 3001 ms 288 KB ok
6 Correct 3001 ms 276 KB ok
7 Correct 3001 ms 276 KB ok
8 Correct 3001 ms 280 KB ok
9 Correct 3001 ms 280 KB ok
10 Correct 3001 ms 280 KB ok
11 Correct 3001 ms 276 KB ok
12 Correct 3001 ms 280 KB ok
13 Correct 3001 ms 280 KB ok
14 Correct 3001 ms 280 KB ok
15 Correct 3000 ms 280 KB ok
16 Correct 3001 ms 276 KB ok
17 Correct 3001 ms 272 KB ok
18 Correct 3001 ms 280 KB ok
19 Correct 3000 ms 280 KB ok
20 Correct 3001 ms 272 KB ok
21 Correct 3001 ms 276 KB ok
22 Correct 3001 ms 276 KB ok
23 Correct 3001 ms 272 KB ok
24 Correct 3001 ms 276 KB ok
25 Correct 3001 ms 272 KB ok
26 Correct 3001 ms 272 KB ok
27 Correct 3001 ms 272 KB ok
28 Correct 3001 ms 272 KB ok
29 Correct 3001 ms 272 KB ok
30 Partially correct 3001 ms 312 KB partial
31 Partially correct 3001 ms 308 KB partial
32 Correct 3001 ms 304 KB ok
33 Correct 3001 ms 292 KB ok
34 Correct 3001 ms 312 KB ok
35 Correct 3001 ms 340 KB ok
36 Correct 3001 ms 308 KB ok
37 Correct 3001 ms 332 KB ok
38 Correct 3001 ms 316 KB ok
39 Correct 3001 ms 320 KB ok
40 Correct 3001 ms 392 KB ok
41 Correct 3001 ms 360 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 272 KB partial
2 Correct 3000 ms 272 KB ok
3 Correct 3001 ms 280 KB ok
4 Correct 3001 ms 292 KB ok
5 Correct 3001 ms 288 KB ok
6 Correct 3001 ms 276 KB ok
7 Correct 3001 ms 276 KB ok
8 Correct 3001 ms 280 KB ok
9 Correct 3001 ms 280 KB ok
10 Correct 3001 ms 280 KB ok
11 Correct 3001 ms 276 KB ok
12 Correct 3001 ms 280 KB ok
13 Correct 3001 ms 280 KB ok
14 Correct 3001 ms 280 KB ok
15 Correct 3000 ms 280 KB ok
16 Correct 3001 ms 276 KB ok
17 Correct 3001 ms 272 KB ok
18 Correct 3001 ms 280 KB ok
19 Correct 3000 ms 280 KB ok
20 Correct 3001 ms 272 KB ok
21 Correct 3001 ms 276 KB ok
22 Correct 3001 ms 276 KB ok
23 Correct 3001 ms 272 KB ok
24 Correct 3001 ms 276 KB ok
25 Correct 3001 ms 272 KB ok
26 Correct 3001 ms 272 KB ok
27 Correct 3001 ms 272 KB ok
28 Correct 3001 ms 272 KB ok
29 Correct 3001 ms 272 KB ok
30 Partially correct 3001 ms 312 KB partial
31 Partially correct 3001 ms 308 KB partial
32 Correct 3001 ms 304 KB ok
33 Correct 3001 ms 292 KB ok
34 Correct 3001 ms 312 KB ok
35 Correct 3001 ms 340 KB ok
36 Correct 3001 ms 308 KB ok
37 Correct 3001 ms 332 KB ok
38 Correct 3001 ms 316 KB ok
39 Correct 3001 ms 320 KB ok
40 Correct 3001 ms 392 KB ok
41 Correct 3001 ms 360 KB ok
42 Partially correct 3020 ms 7376 KB partial
43 Correct 3023 ms 7416 KB ok
44 Partially correct 3052 ms 7572 KB partial
45 Partially correct 3027 ms 7840 KB partial
46 Partially correct 3021 ms 7428 KB partial
47 Execution timed out 4565 ms 12012 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3001 ms 272 KB partial
2 Correct 3000 ms 272 KB ok
3 Correct 3001 ms 280 KB ok
4 Correct 3001 ms 292 KB ok
5 Correct 3001 ms 288 KB ok
6 Correct 3000 ms 272 KB ok
7 Correct 3001 ms 272 KB ok
8 Correct 3275 ms 1992 KB ok
9 Execution timed out 4551 ms 12172 KB Time limit exceeded
10 Halted 0 ms 0 KB -