oj.uz

Submission #1064243

# Submission time Handle Problem Language Result Execution time Memory
1064243 2024-08-18T10:48:20 Z parsadox2 Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 194388 KB 
#include "soccer.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 50 + 10;
int n , best[(1 << 25)];
vector<vector<int>> a;
bool adj[N][N];
bool all[2][(1 << 25)];
int bad_adj[N];

int f(pair<int , int> v)
{
    return v.F * n + v.S;
}

void Add_Edge(pair <int , int> u , pair<int , int> v)
{
    if(a[u.F][u.S] == 1 || a[v.F][v.S] == 1)
        return;
    pair <int , int> x , y;
    x = make_pair(u.F , v.S);
    int ans1 = a[x.F][x.S];
    y = make_pair(v.F , u.S);
    int ans2 = a[y.F][y.S];
    //cout << "____________" << endl;
    for(int i = u.S ; i >= x.S ; i--)
    {
        //cout << 1 << " : " << u.F << " " << i << endl;
        ans1 += a[u.F][i];
    }
    for(int i = u.S ; i <= x.S ; i++)
    {
        //cout << 1 << " : " << u.F << " " << i << endl;
        ans1 += a[u.F][i];
    }
    for(int i = v.S ; i >= y.S ; i--)
    {
        //cout << 2 << " : " << v.F << " " << i << endl;
        ans2 += a[v.F][i];
    }
    for(int i = v.S ; i <= y.S ; i++)
    {
        //cout << 2 << " : " << v.F << " " << i << endl;
        ans2 += a[v.F][i];
    }

    for(int i = u.F ; i >= y.F ; i--)
    {
        //cout << 2 << " : " << i << " " << u.S << endl;
        ans2 += a[i][u.S];
    }
    for(int i = u.F ; i <= y.F ; i++)
    {
        //cout << 1 << " : " << i << " " << u.S << endl;
        ans2 += a[i][u.S];
    }
    for(int i = v.F ; i >= x.F ; i--)
    {
        //cout << 2 << " : " << i << " " << v.S << endl;
        ans1 += a[i][v.S];
    }
    for(int i = v.F ; i <= x.F ; i++)
    {
        //cout << 2 << " : " << i << " " << v.S << endl;
        ans1 += a[i][v.S];
    }

    if(ans1 == 0 || ans2 == 0)
        adj[f(u)][f(v)] = adj[f(v)][f(u)] = true;
}

int biggest_stadium(int nn, vector<std::vector<int>> F)
{
    n = nn;
    a = F;
    for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < n ; j++)  for(int ii = 0 ; ii < n ; ii++)  for(int jj = 0 ; jj < n ; jj++)
    {
        Add_Edge(make_pair(i , j) , make_pair(ii , jj));
    }
    all[0][0] = all[1][0] = true;
    int ans = 0;
    for(int mask = 1 ; mask < (1 << 25) ; mask++)
    {
        int fir = 0;
        for(int i = 0 ; i < 25 ; i++)  if((mask >> i) & 1)
        {
            fir = i;
            break;
        }
        all[0][mask] = all[0][(mask ^ (1 << fir))];
        all[1][mask] = all[1][(mask ^ (1 << fir))];
        for(int i = fir ; i < 25 ; i++)  if((mask >> i) & 1)
        {
            if(!adj[fir][i])
                all[0][mask] = false;
            if(!adj[fir + 25][i + 25])
                all[1][mask] = false;
        }
        if(all[0][mask] || all[1][mask])
            ans = max(ans , __builtin_popcount(mask));
    }
    for(int i = 25 ; i < 50 ; i++)  for(int j = 0 ; j < 25 ; j++)  if(adj[i][j])
        bad_adj[i] |= (1 << j);
    for(int mask = 0 ; mask < (1 << 25) ; mask++)
    {
        if(all[0][mask])
        {
            best[mask] = __builtin_popcount(mask);
            continue;
        }
        for(int i = 0 ; i < 25 ; i++)  if((mask >> i) & 1)
            best[mask] = max(best[mask] , best[(mask ^ (1 << i))]);
    }
    for(int mask = 0 ; mask < (1 << 25) ; mask++)  if(all[1][mask])
    {
        int tmp = (1 << 25) - 1;
        for(int i = 0 ; i < 25 ; i++)  if((mask >> i) & 1)
            tmp &= bad_adj[i + 25];
        ans = max(ans , __builtin_popcount(mask) + best[tmp]);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4548 ms 194388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4556 ms 184916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4556 ms 184916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4548 ms 194388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4548 ms 194388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4548 ms 194388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4548 ms 194388 KB Time limit exceeded
2 Halted 0 ms 0 KB -