Submission #390269

#	Time	Username	Problem	Language	Result	Execution time	Memory
390269		fadi57	Paprike (COI18_paprike)	C++14	11 / 100	490 ms	12376 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mx=1e5+10;
const int mod= 1e9+7 ;
const ll inf=1e9+5;
//***while there is life there is hope

int n,m,k;
int siz[mx];
vector<int> adj[mx];

int arr[mx];
map<pair<int,int>,int>blocked;
int visited[mx];
int dfs(int node,int par){

   int zz=arr[node];
   visited[node]=1;
  for(auto it:adj[node]){
    int aa=min(node,it);int bb=max(node,it);
    int yes=blocked[{aa,bb}];
    if(it==par||yes){continue;}else{

        zz+=dfs(it,node);
    }
  }

return zz;


 }
 map<int,pair<int,int>>edge;
int main() {

cin>>n>>k;int sum2=0;
for(int i=1;i<=n;i++){
    cin>>arr[i];sum2+=arr[i];
}

for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    int aa=min(a,b);int bb=max(a,b);
edge[i]={aa,bb};
    adj[a].push_back(b);
    adj[b].push_back(a);

 }
 if(sum2<=k){cout<<0;return 0;}
if(n<=15){
int sum=0;int ans=n;
int z=n;

for(int i=1;i<(1<<z);i++){
        memset(visited,0,sizeof(visited));
        int tt=0;
        for(int j=0;j<n;j++){

            if((1<<j)&i){

               tt++;
                int a=edge[j].first;
                int b=edge[j].second;
                int aa=min(a,b);int bb=max(a,b);
                blocked[{aa,bb}]=1;
          //  cout<<"test "<<a<<" "<<b<<endl;

            }else{
             int a=edge[j].first;
                int b=edge[j].second;
                int aa=min(a,b);int bb=max(a,b);
                blocked[{aa,bb}]=0;



             }
        }
        int okk=1;
    for(int i=1;i<=n;i++){

        if(visited[i]){continue;}else{

            int summ=dfs(i,0);
            if(summ>k){okk=0;}
        }
    }
    if(okk){
        ans=min(ans,tt);

    }
}
cout<<ans;}else{

int sum=0;int ans=0;
for(int i=1;i<=n;i++){
    sum+=arr[i];
    if(sum>k){sum=arr[i];ans++;}
}
cout<<ans;



 }



 }

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:52:5: warning: unused variable 'sum' [-Wunused-variable]
   52 | int sum=0;int ans=n;
      |     ^~~

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