Rezultati

Up. imeNalogaJezikRezultatČas oddaje
programatorji-2017 Škatle C++ 100/100OK 20. apr '17 @ 17:35

Test Točke Porabljen spomin Porabljen čas Status
#1 6/6 3,129 MiB 0,004 s OK
#2 6/6 3,070 MiB 0,004 s OK
#3 6/6 3,129 MiB 0,004 s OK
#4 6/6 3,125 MiB 0,004 s OK
#5 6/6 3,070 MiB 0,004 s OK
#6 7/7 3,066 MiB 0,004 s OK
#7 7/7 3,137 MiB 0,004 s OK
#8 7/7 3,137 MiB 0,004 s OK
#9 7/7 3,059 MiB 0,004 s OK
#10 7/7 3,141 MiB 0,004 s OK
#11 7/7 3,066 MiB 0,004 s OK
#12 7/7 3,078 MiB 0,010 s OK
#13 7/7 3,074 MiB 0,010 s OK
#14 7/7 3,172 MiB 0,010 s OK
#15 7/7 3,086 MiB 0,004 s OK

Ocenjevani program (skatle.cpp):
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;

#define pb push_back
typedef vector<int> vi;

vi skl[200];
vi vtx[200];
int inDeg[200];

bool canFit(vi& v1, vi& v2, int d){
    for(int i = 0;i < d;i++)
        if(v1[i] <= v2[i])
            return false;
    return true;
}

deque<int> dq;
int main(){
    int n,d,tmp;
    cin>>n>>d;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < d;j++){
            cin>>tmp;
            skl[i].pb(tmp);
        }
        sort(skl[i].begin(),skl[i].end());
    }
      
    
    for(int i = 0;i < n;i++){
        for(int j = 0; j < n;j++){
            if(canFit(skl[i],skl[j],d)){
                vtx[i].pb(j);
                inDeg[j]++;
            }
        }
    }
    
    for(int i = 0;i < n;i++)
        if(inDeg[i] == 0)
            dq.push_back(i);
        
    int level = 0;
    while(!dq.empty()){
        int sz = dq.size();
        level++;
        for(int i = 0;i < sz;i++){
            int top = dq.front();
            dq.pop_front();
            for(int j = 0;j < vtx[top].size();j++)
                if(--inDeg[vtx[top][j]] == 0)
                    dq.push_back(vtx[top][j]);
        }
    }
    cout<<level<<"\n";
    
    return 0;
}