Submission #212873

#	Time	Username	Problem	Language	Result	Execution time	Memory
212873		lmercep	Paprike (COI18_paprike)	C++14	13 / 100	203 ms	43512 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

llint n;
llint k;
llint ljutina[100009];
vector<llint> veze[100009];
llint bio[100009],uk[100009],stv[100009];
llint rez,mak;

 llint dfs(int x){
     uk[x] = ljutina[x];
    for(int i = 0;i<veze[x].size();i++){
        if(bio[veze[x][i]]==0){
                bio[veze[x][i]] = 1;
                uk[x] += dfs(veze[x][i]);
        }
        else{
            //veze[x].erase(veze[x].begin()+i);
            //cout << "brisanje" << endl;
            //i--;
        }
    }
    return uk[x];
 }

 void rijesi(int x){
    bio[x] = 1;
    llint zbroj = ljutina[x];
    vector<llint> stvari,ind;
    map<llint,llint> pomoc;
    //cout << "Ispis: " << x << endl;
    for(int i = 0;i<veze[x].size();i++){
    	
        if(bio[veze[x][i]]==0){
           // cout << veze[x][i] << ' ' << bio[veze[x][i]] << ' ' << x << ' ';
            bio[veze[x][i]] = 1;
            stvari.push_back(uk[veze[x][i]]);
            pomoc[uk[veze[x][i]]] = veze[x][i];
          //  cout << stvari[i]<< ' ' << uk[veze[x][i]] << ' ' << pomoc[stvari[i]] << "\n";
        }
    }
    sort(stvari.begin(),stvari.end());
    for(int i = 0;i<stvari.size();i++){
        ind.push_back(pomoc[stvari[i]]);
      //  cout << stvari[i]<< ' ' << pomoc[stvari[i]] << ' ' << ind[i]<< ' ' << x <<' ' <<pomoc[12] << "\n";
    }
    for(int i = 0;i<stvari.size();i++){
        if(zbroj+stvari[i]>k){
            if(zbroj+ljutina[ind[i]]<=k){
                k-=zbroj;
                mak += zbroj;
                rijesi(ind[i]);
                k+=zbroj;
                mak -= zbroj;
                zbroj += stv[ind[i]];
            }
            else{
          //      cout << x << ' ' << ind[i] << "\n";
                rez++;
                if(stvari[i]>k+mak){
                    k+=mak;
                    int zap = mak;
                    mak = 0;
                    rijesi(ind[i]);
                    mak = zap;
                    k-=mak;
                }
            }
        }
        else{
            zbroj += stvari[i];
        }
    }
    stv[x] = zbroj;
 }

int main(){
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        llint a;
        cin >> a;
        ljutina[i] = a;
    }
    //ljutina[x] -> kaze koliko je paprika x ljuta
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        veze[a-1].push_back(b-1);
        veze[b-1].push_back(a-1);
    }
    bio[0] = 1;
    dfs(0);
    
    rez = 0;
    memset(bio,0,sizeof(bio));
    bio[0] = 1;
    mak = 0;
    rijesi(0);
   // cout << "\n";
   // for(int i = 0;i<n;i++){
       // cout << uk[i] << ' ' << stv[i] << "\n";
  //  }
    cout << rez;
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'llint dfs(int)':
paprike.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<veze[x].size();i++){
                   ~^~~~~~~~~~~~~~~
paprike.cpp: In function 'void rijesi(int)':
paprike.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<veze[x].size();i++){
                   ~^~~~~~~~~~~~~~~
paprike.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<stvari.size();i++){
                   ~^~~~~~~~~~~~~~
paprike.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<stvari.size();i++){
                   ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49