Submission #212916

#	Time	Username	Problem	Language	Result	Execution time	Memory
212916		Lukap	Paprike (COI18_paprike)	C++14	0 / 100	158 ms	14816 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

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

 int 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);
            i--;
        }
    }
    return uk[x];
 }

 void rijesi(int x){
    bio[x] = 1;
    long long zbroj = ljutina[x];
    vector<long long> stvari,ind;
    map<long long,long long> pomoc;
    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++){
        int a;
        cin >> a;
        ljutina[i] = a;
    }
    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 'int dfs(int)':
paprike.cpp:13: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:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<veze[x].size();i++){
                   ~^~~~~~~~~~~~~~~
paprike.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<stvari.size();i++){
                   ~^~~~~~~~~~~~~~
paprike.cpp:45: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: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49