제출 #1137115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137115		Zbyszek99	Game (eJOI20_game)	C++20	100 / 100	1 ms	584 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int dp[445][445][2][2];
int rep_[445];
int siz_[445];
bool is_path[445];
int sides[445];

int fint(int v)
{
    if(rep_[v] == v) return v;
    rep_[v] = fint(rep_[v]);
    return rep_[v];
}

void onion(int a, int b)
{
    a = fint(a);
    b = fint(b);
    if(a == b) return;
    siz_[b] += siz_[a];
    rep_[a] = b;
    is_path[b] = is_path[b] || is_path[a];
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m;
    cin >> n >> m;
    rep(i,n*m)
    {
        rep_[i] = i;
        siz_[i] = 1;
    }
    rep(i,n+1)
    {
        rep(j,m)
        {
            char z;
            cin >> z;
            if(z == '1')
            {
                if(i!=n)
                {
                    sides[i*m+j]++;
                }
                if(i!=0)
                {
                    sides[(i-1)*m+j]++;
                }
            }
            else
            {
                if(i > 0 && i < n)
                {
                    onion(i*m+j,(i-1)*m+j);
                }
                if(i == 0)
                {
                    is_path[fint(i*m+j)] = 1;
                }
                if(i == n)
                {
                    is_path[fint((i-1)*m+j)] = 1;
                }
            }
        }
    }
    rep(i,n)
    {
        rep(j,m+1)
        {
            char z;
            cin >> z;
            if(z == '1')
            {
                if(j!=m)
                {
                    sides[i*m+j]++;
                }
                if(j!=0)
                {
                    sides[i*m+j-1]++;
                }
            }
            else
            {
                if(j > 0 && j < m)
                {
                    onion(i*m+j,i*m+j-1);
                }
                if(j == 0)
                {
                    is_path[fint(i*m+j)] = 1;
                }
                if(j == m)
                {
                    is_path[fint(i*m+j-1)] = 1;
                }
            }
        }
    }
    vector<int> paths;
    vector<int> cycles;
    rep(i,n*m)
    {
        if(fint(i) == i && sides[i] != 4)
        {
            if(is_path[i])
            {
                paths.pb(siz_[i]);
            }
            else
            {
                cycles.pb(siz_[i]);
            }
        }
    }
    sort(all(paths));
    sort(all(cycles));
    for(int p = siz(paths); p >= 0; p--)
    {
        //cout << comps[i] << " comps\n";
        for(int c = siz(cycles); c >= 0; c--)
        {
            if(p == siz(paths) && c == siz(cycles))
            {
                continue;
            }
            dp[p][c][0][0] = -1e5;
            dp[p][c][0][1] = -1e5;
            dp[p][c][1][0] = 1e5;
            dp[p][c][1][1] = 1e5;
            
            if(p < siz(paths))
            {
                // 0 0
                if(p == siz(paths)-1 && c == siz(cycles)) dp[p][c][0][0] = paths[p];
                if(p+1 < siz(paths))
                {
                    dp[p][c][0][0] = max(dp[p][c][0][0],dp[p+1][c][1][0] + paths[p]);
                }
                if(c < siz(cycles))
                {
                    dp[p][c][0][0] = max(dp[p][c][0][0],dp[p+1][c][1][1] + paths[p]);
                }
                if(paths[p] > 2)
                {
                    int w2 = 1e5;
                    if(p + 1 < siz(paths))
                    {
                        w2 = min(w2,dp[p+1][c][0][0]);
                    }
                    if(c < siz(cycles))
                    {
                        w2 = min(w2,dp[p+1][c][0][1]);
                    }
                    if(w2 != 1e5)
                    dp[p][c][0][0] = max(dp[p][c][0][0],w2 + paths[p] - 4);
                }
                //1 0
                if(p == siz(paths)-1 && c == siz(cycles)) dp[p][c][1][0] = -paths[p];
                if(p + 1 < siz(paths))
                {
                    dp[p][c][1][0] = min(dp[p][c][1][0],dp[p+1][c][0][0] - paths[p]);
                }
                if(c < siz(cycles))
                {
                    dp[p][c][1][0] = min(dp[p][c][1][0],dp[p+1][c][0][1] - paths[p]);
                }
                if(paths[p] > 2)
                {
                    int w2 = -1e5;
                    if(p + 1 < siz(paths))
                    {
                        w2 = max(w2,dp[p+1][c][1][0]);
                    }
                    if(c < siz(cycles))
                    {
                        w2 = max(w2,dp[p+1][c][1][1]);
                    }
                    if(w2 != -1e5)
                    dp[p][c][1][0] = min(dp[p][c][1][0],w2 - paths[p] + 4);
                }
            }
            if(c < siz(cycles))
            {
                // 0 1
                if(c == siz(cycles)-1 && p == siz(paths)) dp[p][c][0][1] = cycles[c];
                if(p < siz(paths))
                {
                    dp[p][c][0][1] = max(dp[p][c][0][1],dp[p][c+1][1][0]+cycles[c]);
                }
                if(c + 1 < siz(cycles))
                {
                    dp[p][c][0][1] = max(dp[p][c][0][1],dp[p][c+1][1][1]+cycles[c]);
                }
                int w2 = 2e5;
                if(p < siz(paths))
                {
                    w2 = min(w2,dp[p][c+1][0][0]);
                }
                if(c + 1 < siz(cycles))
                {
                    w2 = min(w2,dp[p][c+1][0][1]);
                }
                if(w2 != 2e5)
                dp[p][c][0][1] = max(dp[p][c][0][1],w2 + cycles[c] - 8);
                // 1 1
                if(c == siz(cycles)-1 && p == siz(paths)) dp[p][c][1][1] = -cycles[c];
                if(p < siz(paths))
                {
                    dp[p][c][1][1] = min(dp[p][c][1][1],dp[p][c+1][0][0]-cycles[c]);
                }
                if(c + 1 < siz(cycles))
                {
                    dp[p][c][1][1] = min(dp[p][c][1][1],dp[p][c+1][0][1]-cycles[c]);
                }
                w2 = -2e5;
                if(p < siz(paths))
                {
                    w2 = max(w2,dp[p][c+1][1][0]);
                }
                if(c + 1 < siz(cycles))
                {
                    w2 = max(w2,dp[p][c+1][1][1]);
                }
                if(w2 != -2e5)
                dp[p][c][1][1] = min(dp[p][c][1][1],w2 - cycles[c] + 8);
            }
         //   cout << "paths: " << p << " cycles: " << c << "\n";
         //   cout << dp[p][c][0][0] << " 00\n";
         //   cout << dp[p][c][0][1] << " 01\n";
         //   cout << dp[p][c][1][0] << " 10\n";
        //    cout << dp[p][c][1][1] << " 11\n\n";   
        }
    }
  //  cout << siz(paths) << " " << siz(cycles) << " sizy\n";
  //  forall(it,paths) cout << it << " path\n";
  //  forall(it,cycles) cout << it << " cycle\n";
    if(siz(paths) == 0 && siz(cycles) == 0)
    {
        cout << 0;
        return 0;
    }
    cout << max((siz(paths) != 0 ? dp[0][0][1][0] : (int)-2e5),(siz(cycles) != 0 ? dp[0][0][1][1]: (int)-2e5)) << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20