oj.uz

답안 #655817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655817 2022-11-05T16:18:43 Z someone Bomb (IZhO17_bomb) C++14
30 / 100
 1000 ms 101908 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25556 KB Output is correct
2 Correct 11 ms 25556 KB Output is correct
3 Correct 11 ms 25684 KB Output is correct
4 Correct 11 ms 25640 KB Output is correct
5 Correct 11 ms 25684 KB Output is correct
6 Correct 12 ms 25556 KB Output is correct
7 Correct 11 ms 25632 KB Output is correct
8 Incorrect 11 ms 25568 KB Output isn't correct
9 Incorrect 14 ms 25624 KB Output isn't correct
10 Correct 11 ms 25628 KB Output is correct
11 Incorrect 11 ms 25520 KB Output isn't correct
12 Correct 11 ms 25556 KB Output is correct
13 Correct 11 ms 25600 KB Output is correct
14 Correct 15 ms 25556 KB Output is correct
15 Incorrect 12 ms 25524 KB Output isn't correct
16 Correct 13 ms 25556 KB Output is correct
17 Incorrect 12 ms 25556 KB Output isn't correct
18 Correct 11 ms 25568 KB Output is correct
19 Incorrect 11 ms 25556 KB Output isn't correct
20 Incorrect 12 ms 25568 KB Output isn't correct
21 Correct 11 ms 25540 KB Output is correct
22 Correct 11 ms 25528 KB Output is correct
23 Incorrect 11 ms 25596 KB Output isn't correct
24 Incorrect 13 ms 25584 KB Output isn't correct
25 Incorrect 12 ms 25684 KB Output isn't correct
26 Correct 13 ms 25812 KB Output is correct
27 Correct 39 ms 26948 KB Output is correct
28 Correct 13 ms 25812 KB Output is correct
29 Correct 31 ms 26964 KB Output is correct
30 Incorrect 21 ms 26584 KB Output isn't correct
31 Incorrect 17 ms 26272 KB Output isn't correct
32 Incorrect 17 ms 26276 KB Output isn't correct
33 Incorrect 24 ms 26584 KB Output isn't correct
34 Correct 14 ms 25748 KB Output is correct
35 Incorrect 17 ms 26196 KB Output isn't correct
36 Incorrect 55 ms 28096 KB Output isn't correct
37 Incorrect 11 ms 25628 KB Output isn't correct
38 Execution timed out 1051 ms 101712 KB Time limit exceeded
39 Incorrect 11 ms 25556 KB Output isn't correct
40 Incorrect 165 ms 35476 KB Output isn't correct
41 Incorrect 12 ms 25556 KB Output isn't correct
42 Incorrect 12 ms 25684 KB Output isn't correct
43 Execution timed out 1058 ms 101908 KB Time limit exceeded
44 Incorrect 37 ms 27092 KB Output isn't correct
45 Incorrect 981 ms 68960 KB Output isn't correct
46 Correct 952 ms 68876 KB Output is correct
47 Incorrect 984 ms 68844 KB Output isn't correct
48 Incorrect 881 ms 68904 KB Output isn't correct
49 Execution timed out 1053 ms 101668 KB Time limit exceeded
50 Incorrect 957 ms 68880 KB Output isn't correct
51 Incorrect 974 ms 69140 KB Output isn't correct
52 Incorrect 925 ms 69056 KB Output isn't correct
53 Incorrect 908 ms 68964 KB Output isn't correct
54 Correct 487 ms 52500 KB Output is correct
55 Correct 463 ms 52616 KB Output is correct
56 Execution timed out 1051 ms 101560 KB Time limit exceeded
57 Correct 455 ms 52276 KB Output is correct
58 Correct 482 ms 52236 KB Output is correct
59 Correct 446 ms 52280 KB Output is correct
60 Correct 815 ms 68656 KB Output is correct
61 Execution timed out 1058 ms 101292 KB Time limit exceeded
62 Execution timed out 1016 ms 101228 KB Time limit exceeded
63 Execution timed out 1078 ms 101248 KB Time limit exceeded
64 Correct 460 ms 51904 KB Output is correct
65 Incorrect 850 ms 68340 KB Output isn't correct
66 Incorrect 868 ms 68520 KB Output isn't correct
67 Execution timed out 1024 ms 68404 KB Time limit exceeded
68 Execution timed out 1052 ms 100976 KB Time limit exceeded
69 Correct 429 ms 51664 KB Output is correct
70 Incorrect 146 ms 37188 KB Output isn't correct
71 Incorrect 304 ms 43468 KB Output isn't correct
72 Incorrect 429 ms 51772 KB Output isn't correct
73 Incorrect 446 ms 51748 KB Output isn't correct
74 Incorrect 467 ms 51716 KB Output isn't correct
75 Incorrect 459 ms 51768 KB Output isn't correct
76 Incorrect 470 ms 51664 KB Output isn't correct
77 Incorrect 484 ms 51664 KB Output isn't correct
78 Incorrect 486 ms 51772 KB Output isn't correct
79 Incorrect 112 ms 35484 KB Output isn't correct
80 Incorrect 116 ms 35644 KB Output isn't correct
81 Incorrect 144 ms 37328 KB Output isn't correct
82 Incorrect 525 ms 51388 KB Output isn't correct
83 Incorrect 507 ms 51132 KB Output isn't correct
84 Incorrect 112 ms 34860 KB Output isn't correct
85 Incorrect 474 ms 51240 KB Output isn't correct
86 Execution timed out 1062 ms 99632 KB Time limit exceeded
87 Correct 467 ms 50348 KB Output is correct
88 Incorrect 503 ms 50412 KB Output isn't correct
89 Incorrect 695 ms 66964 KB Output isn't correct
90 Incorrect 269 ms 39936 KB Output isn't correct
91 Incorrect 570 ms 66708 KB Output isn't correct
92 Incorrect 689 ms 66776 KB Output isn't correct
93 Execution timed out 1071 ms 98920 KB Time limit exceeded
94 Incorrect 706 ms 66120 KB Output isn't correct
95 Incorrect 534 ms 49596 KB Output isn't correct
96 Incorrect 522 ms 49684 KB Output isn't correct
97 Execution timed out 1083 ms 98676 KB Time limit exceeded
98 Incorrect 505 ms 49324 KB Output isn't correct
99 Incorrect 673 ms 65780 KB Output isn't correct
100 Execution timed out 1097 ms 98440 KB Time limit exceeded