Submission #1064243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064243		parsadox2	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	4556 ms	194388 KiB

soccer

#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
• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30