Submission #1025889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025889		vjudge1	Paprike (COI18_paprike)	C++17	11 / 100	30 ms	440 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
const int MAX_N=20;
bool visited[MAX_N];
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];
    }
    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;
}

Compilation message (stderr)

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

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