#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
int R, S;
vi rnk, padre, taken;
vector<set<int>> myComponents;
map<int, vector<int>> componentinRow;
vs mapa;
vvi dp;
vi SegTree, oil;
int root(int node){
if(padre[node] == node) return node;
else return padre[node] = root(padre[node]);
}
void mergeComponents(int x1, int y1, int x2, int y2){
if(mapa[x2][y2] == '.')return;
int val1 = x1*S + y1;
int val2 = x2*S + y2;
int root1 = root(val1);
int root2 = root(val2);
if(root1 == root2) return;
padre[root1] = root2;
rnk[root2] += rnk[root1];
}
void traversal(){
unordered_map<char, int> M;
M['1'] = 1;
M['2'] = 2;
M['3'] = 3;
M['4'] = 4;
M['5'] = 5;
M['6'] = 6;
M['7'] = 7;
M['8'] = 8;
M['9'] = 9;
for(int i = 0; i < R*S; ++i){
int y = i/S;
int x = i%S;
if(mapa[y][x] != '.') rnk[i] = M[mapa[y][x]];
}
for(int i = 0; i < R; ++i){
for(int j = 0; j < S; ++j){
if(mapa[i][j] == '.') continue;
if(i > 0) mergeComponents(i, j, i-1, j);
if(j > 0) mergeComponents(i, j, i, j-1);
if(i < R-1) mergeComponents(i, j, i+1, j);
if(j < S-1) mergeComponents(i, j, i, j+1);
}
}
}
void setUpComponents(){
for(int i = 0; i < R; ++i){
for(int j = 0; j < S; ++j){
if(mapa[i][j] != '.') {
myComponents[j].insert(root(i*S+j));
if(componentinRow.find(root(i*S+j)) != componentinRow.end()) componentinRow[root(i*S+j)].push_back(j);
else componentinRow[root(i*S+j)]= {j};
}
}
}
}
void buildTree(int node, int leftBound, int rightBound){
if(leftBound > rightBound) return;
if(leftBound == rightBound){
SegTree[node] = leftBound;
return;
}
int mid = leftBound + (rightBound - leftBound)/2;
buildTree(2*node, leftBound, mid);
buildTree(2*node+1, mid+1, rightBound);
int Lval = oil[SegTree[2*node]];
int Rval = oil[SegTree[2*node+1]];
if(Lval > Rval) SegTree[node] = SegTree[2*node];
else SegTree[node] = SegTree[2*node+1];
}
void modify(int node, int left, int right, int pos, int modification){
if(left > pos or right < pos) return;
if(left == right and left == pos){
SegTree[node] == pos;
oil[pos] -= modification;
return;
}
if(left > right) return;
int mid = left + (right - left)/2;
modify(2*node, left, mid, pos, modification);
modify(2*node+1, mid+1, right, pos, modification);
int Lval = oil[SegTree[2*node]];
int Rval = oil[SegTree[2*node+1]];
if(Lval > Rval) SegTree[node] = SegTree[2*node];
else SegTree[node] = SegTree[2*node+1];
}
int main(){
cin >> R >> S;
mapa = vs(R);
for(int i = 0; i < R; ++i) cin >> mapa[i];
padre = vi(R*S);
for(int i = 0; i < R*S; ++i) padre[i] = i;
rnk = vi(R*S, 0);
traversal();
myComponents = vector<set<int>>(S);
setUpComponents();
oil = vi(S);
for(int i = 0; i < S; ++i){
for(auto it = myComponents[i].cbegin(); it != myComponents[i].cend(); ++it){
//cout << i << " " << rnk[*it] << endl;
oil[i]+=rnk[*it];
}
}
SegTree = vi(4*S);
buildTree(1, 0, S-1);
int prev = 0;
for(int i = 0; i < S; ++i){
int bestOil = SegTree[1];
prev += oil[bestOil];
cout << prev << endl;
for(auto it = myComponents[bestOil].cbegin(); it != myComponents[bestOil].cend(); ++it){
//cout << *it << endl;
for(int take: componentinRow[*it]) {
//cout << *it << " " << take << endl;
modify(1, 0, S-1, take, rnk[*it]);
//if(take != bestOil)myComponents[take].erase(it);
}
componentinRow[*it] = {};
}
myComponents[bestOil].clear();
}
return 0;
}
Compilation message
nafta.cpp: In function 'void modify(int, int, int, int, int)':
nafta.cpp:91:23: warning: value computed is not used [-Wunused-value]
91 | SegTree[node] == pos;
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
