Rezultati

Up. imeNalogaJezikRezultatČas oddaje
tab-2019 Barvanje drevesa C++ 100/100OK 24. apr '19 @ 19:13

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 3,043 MiB 0,004 s OK
#2 [več] 10/10 3,031 MiB 0,000 s OK
#3 [več] 10/10 3,129 MiB 0,000 s OK
#4 [več] 10/10 3,031 MiB 0,000 s OK
#5 [več] 10/10 3,031 MiB 0,000 s OK
#6 [več] 10/10 3,297 MiB 0,004 s OK
#7 [več] 10/10 3,145 MiB 0,004 s OK
#8 [več] 10/10 3,297 MiB 0,000 s OK
#9 [več] 10/10 3,133 MiB 0,010 s OK
#10 [več] 10/10 3,145 MiB 0,000 s OK

Ocenjevani program (main.cpp):
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;
class v;
vector<v> voz;

class v{
public:
    int l;
    int d;
    int p;
    int ls;
    int ds;
    int depth;
    int color=-1;
    vector<bool> colors;
    v(){
        colors=vector<bool>(5,false);
        ls=0;
        ds=0;
        l=0;
        d=0;
        p=-1;
    }

    int fc(){
        for(int i=0;i<5;++i){
            if(!colors[i]) return i;
        }
        return -1;
    }

    void mc(int c){
        color=c;
        if(l!=0) voz[l].colors[c]=true;
        if(d!=0) voz[d].colors[c]=true;
        if(ls!=0) voz[ls].colors[c]=true;
        if(ds!=0) voz[ds].colors[c]=true;
    }
};

int main()
{
    int n;
    cin>> n;
    voz=vector<v>(n+1,v());
    for(int i=0;i<n;++i){
        int l,d;
        cin>>l>>d;
        voz[i+1].l=l;
        voz[i+1].d=d;
        voz[l].p=i+1;
        voz[d].p=i+1;
    }
    int r=1;
    for(int i=1;i<n+1;++i){
        if(voz[i].p==-1) r=i;
    }
    vector<int> q;
    q.push_back(r);
    int in=0;
    voz[1].depth=0;
    while(in<q.size()){
        int c=q[in];
        if(voz[c].l!=0){
            int l=voz[c].l;
            voz[l].depth=voz[c].depth+1;
            if(voz[q.back()].depth==voz[l].depth){
                voz[q.back()].ds=l;
                voz[l].ls=q.back();
            }
            q.push_back(l);
        }
        if(voz[c].d!=0){
            int l=voz[c].d;
            voz[l].depth=voz[c].depth+1;
            if(voz[q.back()].depth==voz[l].depth){
                voz[q.back()].ds=l;
                voz[l].ls=q.back();
            }
            q.push_back(l);
        }
        in++;
    }
    q.clear();
    q.push_back(r);
    in=0;
    while(in<q.size()){
        int c=q[in];
        int cc=voz[c].fc();
        voz[c].mc(cc);
        if(voz[c].l!=0){
            q.push_back(voz[c].l);
        }
        if(voz[c].d!=0){
            q.push_back(voz[c].d);
        }
        in++;
    }
    for(int i=1;i<n+1;++i){
        cout<<voz[i].color+1<<" ";
    }
    return 0;
}