| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 655817 |
2022-11-05T16:18:43 Z |
someone |
Bomb (IZhO17_bomb) |
C++14 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
