oj.uz

Submission #632713

# Submission time Handle Problem Language Result Execution time Memory
632713 2022-08-20T16:47:29 Z a_aguilo Nafta (COI15_nafta) C++14
0 / 100
 1 ms 340 KB 
#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;

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -