Submission #101617

#	Time	Username	Problem	Language	Result	Execution time	Memory
101617		errorgorn	Chase (CEOI17_chase)	C++14	0 / 100	3 ms	384 KiB

chase

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int chase=0;
int n,v;
int arr[11];
bool am[11][11];
void print(vector<int> i){
    for (int x=0;x<i.size();x++) printf("%d ",i[x]);
    printf("\n");
}
int bits(int x){
    int ans=0;
    while (x!=0){
        x-=(x&(-x));
        ans++;
    }
    return ans;
}
void simulate (vector<int> i){
    int pigeons[11];
    int ans;
    for (int x=0;x<(1<<i.size());x++){
        if (bits(x)<=v){
            ans=0;
            for (int y=1;y<=n;y++) pigeons[y]=arr[y];
            for (int y=0;y<i.size();y++){
                ans-=pigeons[i[y]];
                if ( (x&(1<<y))!=0){
                    for (int z=1;z<=n;z++){
                        if (am[z][i[y]]) pigeons[i[y]]+=pigeons[z],pigeons[z]=0;
                    }
                }
            }
            for (int y=0;y<i.size();y++){
                ans+=pigeons[i[y]];
            }
            if (ans>chase){
                chase=ans;
                /*printf("%d: ",x);
                print(i);*/
            }
        }
    }
}
void dfs(vector<int> i){
    simulate(i);
    i.push_back(-1);
    for (int x=0;x<n;x++){
        if (am[x][i[i.size()-2]] && x!=i[i.size()-3]){
            i[i.size()-1]=x;
            dfs(i);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    int a,b;
    scanf("%d%d",&n,&v);
    for (int x=1;x<=n;x++){
        scanf("%d",&arr[x]);
    }
    for (int x=1;x<n;x++){
        scanf("%d%d",&a,&b);
        am[a][b]=true;
        am[b][a]=true;
    }
    vector<int> perm(1);
    for (int x=1;x<=n;x++){
        perm[0]=x;
        dfs(perm);
    }
    printf("%d\n",chase);
}

Compilation message (stderr)

chase.cpp: In function 'void print(std::vector<int>)':
chase.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=0;x<i.size();x++) printf("%d ",i[x]);
                  ~^~~~~~~~~
chase.cpp: In function 'void simulate(std::vector<int>)':
chase.cpp:28:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int y=0;y<i.size();y++){
                          ~^~~~~~~~~
chase.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int y=0;y<i.size();y++){
                          ~^~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&v);
     ~~~~~^~~~~~~~~~~~~~
chase.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
chase.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30