Rezultati

Up. imeNalogaJezikRezultatČas oddaje
proof-is-trivial-2019 Barvanje drevesa C++ 100/100OK 24. apr '19 @ 18:55

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 3,191 MiB 0,000 s OK
#2 [več] 10/10 3,188 MiB 0,000 s OK
#3 [več] 10/10 3,191 MiB 0,000 s OK
#4 [več] 10/10 3,035 MiB 0,004 s OK
#5 [več] 10/10 3,039 MiB 0,004 s OK
#6 [več] 10/10 3,234 MiB 0,000 s OK
#7 [več] 10/10 3,094 MiB 0,004 s OK
#8 [več] 10/10 3,270 MiB 0,010 s OK
#9 [več] 10/10 3,270 MiB 0,000 s OK
#10 [več] 10/10 3,070 MiB 0,004 s OK

Ocenjevani program (drevesa.cpp):
#include <iostream>
#include <vector>

struct drevo {
    drevo* left;
    drevo* right;
    drevo* parent;
    int barva;

    drevo() {
        left = nullptr;
        right = nullptr;
        parent = nullptr;
        barva = 0;
    }

};

int main() {
    drevo* root; // ?
    int amount;
    std::cin >> amount;
    std::vector<drevo> all(amount);
    //all[0] = new drevo();
    //all[1] = new drevo();
    int levo, desno;
    for (int i = 0; i < amount; ++i) {
        std::cin >> levo >> desno;
        if(levo) {
            all[i].left = &all[levo-1];
            all[levo-1].parent = &all[i];
        }
        if(desno) {
            all[i].right = &all[desno-1];
            all[desno-1].parent = &all[i];
        }
    }
    // tree constructed
    root = &all[0];
    // find root
    while (root->parent) {
        root = root->parent;
    }
    root->barva = 1;
    // construct x and y
    std::vector<std::vector<drevo*>> coordinates;
    std::vector<drevo*> cur;
    cur.push_back(root);
    coordinates.push_back(cur);
    bool flag = false;
    if (root->left or root->right) {
        flag = true;
    }
    int level = 1;
    while (flag) {
        cur.clear();
        flag = false;
        for(auto previous: coordinates[level-1]) {
            if (previous->left) {
                cur.push_back(previous->left);
                flag = true;
            }
            if (previous->right) {
                cur.push_back(previous->right);
                flag = true;
            }
        }
        ++level;
        coordinates.push_back(cur);
    }
    
    root->barva = 1;
    // coordinates constructed
    for (int i = 1; i < level; ++i) {
        for (int j = 0; j < coordinates[i].size(); ++j) {
            if (j == 0) { // if first in x direction
                if (coordinates[i][0]->parent->barva == 1)
                    coordinates[i][0]->barva = 2;
                else
                    coordinates[i][0]->barva = 1;
                continue;
            }
            int barva[] = {1,2,3};
            barva[coordinates[i][j]->parent->barva -1] = 0;
            barva[coordinates[i][j-1]->barva -1] = 0;
            for (int neki = 0; neki < 3; ++neki) {
                if (barva[neki]) {
                    coordinates[i][j]->barva = barva[neki];
                    break;
                }
            }
        }
    }
    for (auto i: all) {
        std::cout << i.barva << " ";
    }
    return 0;
}