Submission #655817

#	Time	Username	Problem	Language	Result	Execution time	Memory
655817		someone	Bomb (IZhO17_bomb)	C++14	30 / 100	1097 ms	101908 KiB

bomb

#include <bits/stdc++.h>
//#define int long long
using namespace std;

struct Alien {
    int t, id;
};
 
const int N = 2500 + 42, INF = 1e9 + 42;

bool alien[N*N];
vector<Alien> add;
int n, m, t[N], sz[N*N];

int F(int i) {
    if(sz[i] < 0)
        return i;
    return sz[i] = F(sz[i]);
}

inline int getSz(int i) {
    return -sz[F(i)];
}

void U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b)
        return;
    if(-sz[a] < -sz[b])
        swap(a, b);
    sz[a] += sz[b];
    sz[b] = a;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    for(int i = 0; i < N*N; i++)
        sz[i] = -1;
    
    cin >> n >> m;
    
    n++, m++;
    for(int i = 1; i < n; i++)
        for(int j = 1; j < m; j++) {
            char c; cin >> c;
            alien[m * i + j] = (c == '1');
        }
    
    int minLen = INF;
    for(int i = 1; i < n; i++)
        for(int j = 1; j < m; j++)
            if(alien[m * i + j]) {
                int id = m * i + j;
                t[j] = t[j-1] + 1;
                alien[id] = false;
                add.push_back({t[j], id});
                if(!alien[id+1])
                    minLen = min(minLen, t[j]);
            } else {
                t[j] = 0;
            }
    
    sort(add.begin(), add.end(),
    [](Alien a, Alien b) {
        if(a.t == b.t)
            return a.id < b.id;
        return a.t > b.t;
    });
    
    multiset<int> len;
    int ans = 0, l = (int)add.size();
    for(int i = 0; i < l; i++) {
        int j = add[i].id;
        alien[j] = true;
        if(alien[j - m]) {
            len.erase(len.find(getSz(j - m)));
            U(j - m, j);
        }
        if(alien[j + m]) {
            len.erase(len.find(getSz(j + m)));
            U(j + m, j);
        }
        len.insert(getSz(j));
        if(add[i].t <= minLen && (i == l-1 || add[i+1].t < add[i].t)) {
            auto it = len.begin();
            ans = max(ans, (*it) * add[i].t);
        }
    }
    cout << ans;
}

• Subtask 1: 30 / 100