Submission #1025958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025958		vjudge1	Paprike (COI18_paprike)	C++17	24 / 100	71 ms	17312 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
const int MAX_N=100001;
bool visited[16];
int a[MAX_N];
set<int>tree[MAX_N];

long long int bfs(int root)
{
    long long rez=0;
    queue<int>q;
    q.push(root);
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        if(visited[w])
            continue;
        visited[w]=1;
        rez+=a[w];
        for(auto it=tree[w].begin(); it!=tree[w].end(); it++)
        {
            q.push(*it);
        }
    }
    return rez;
}

int main()
{
    int n;
    long long k;
    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    if(n<=15)
    {
        vector<pair<int, int>>edges;
        for(int i=0; i<n-1; i++)
        {
            int aa, bb;
            cin>>aa>>bb;
            aa--;
            bb--;
            edges.push_back(make_pair(aa, bb));
            tree[aa].insert(bb);
            tree[bb].insert(aa);
        }
        int rez=INT_MAX;
        for(int ii=0; ii<(1ll<<(n-1)); ii++)
        {
            memset(visited, 0, sizeof(visited));
            vector<int>v;
            for(int j=0; j<n-1; j++)
            {
                if((1<<j) & ii)
                {
                    v.push_back(j);
                }
            }
            bool kiki=0;
            if(v.size()==2)
                kiki=1;
            for(int i=0; i<v.size(); i++)
            {
                tree[edges[v[i]].first].erase(edges[v[i]].second);
                tree[edges[v[i]].second].erase(edges[v[i]].first);
            }
            long long int maxx=INT_MIN;
            for(int i=0; i<n; i++)
            {
                if(!visited[i])
                {
                    long long int aa=bfs(i);
                    maxx=max(maxx, aa);
                }
            }
            if(maxx<=k)
            {
                rez=min(rez, (int)v.size());
            }
            for(int i=0; i<v.size(); i++)
            {
                tree[edges[v[i]].first].insert(edges[v[i]].second);
                tree[edges[v[i]].second].insert(edges[v[i]].first);
            }
        }
        cout<<rez;
        return 0;
    }
    for(int i=0; i<n-1; i++)
    {
        int aa, bb;
        cin>>aa>>bb;
        aa--; bb--;
        tree[aa].insert(bb);
        tree[bb].insert(aa);
    }
    int root;
    for(int i=0; i<n; i++)
    {
        if(tree[i].size()==1)
        {
            root=i;
            break;
        }
    }
    int niza[n], idx=0;
    queue<int>q;
    q.push(root);
    bool vis[n];
    memset(vis, 0, sizeof(vis));
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        vis[w]=1;
        niza[idx]=a[w];
        idx++;
        for(auto it=tree[w].begin(); it!=tree[w].end(); it++)
        {
            if(!vis[*it])
                q.push(*it);
        }
    }
    int sum=0, rez=0;
    for(int i=0; i<n; i++)
    {
        sum+=niza[i];
        if(sum>k)
        {
            rez++;
            sum=niza[i];
        }
    }
    cout<<rez;

    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int i=0; i<v.size(); i++)
      |                          ~^~~~~~~~~
paprike.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0; i<v.size(); i++)
      |                          ~^~~~~~~~~
paprike.cpp:64:18: warning: variable 'kiki' set but not used [-Wunused-but-set-variable]
   64 |             bool kiki=0;
      |                  ^~~~

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