Submission #561236

#	Time	Username	Problem	Language	Result	Execution time	Memory
561236		fatemetmhr	Chase (CEOI17_chase)	C++17	20 / 100	4064 ms	9944 KiB

chase

#include <bits/stdc++.h>

using namespace std;

typedef long long    ll;
typedef pair<ll, ll> pll;

#define pb      push_back
#define all(x)  x.begin(), x.end()
#define fi      first
#define se      second
#define mp      make_pair

const int maxn5 = 1e5 + 10;
const int ssq   = 320;
const ll  inf   = 1e18;


ll h[maxn5], have[maxn5];
ll a[maxn5], lim, ans = 0, av[maxn5];
vector <int> adj[maxn5], ver;
int par[maxn5];

inline void dfs(int v){
    for(auto u : adj[v]) if(u != par[v]){
        par[u] = v;
        dfs(u);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n >> lim;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        par[i] = -1;
        dfs(i);
        int v = j;
        ver.clear();
        while(v != -1){
            ver.pb(v);
            v = par[v];
        }
        reverse(all(ver));
        for(int mask = 0; mask < (1 << ver.size()); mask++) if(__builtin_popcount(mask) <= lim){
            ll jer = 0;
            for(int i = 0; i < n; i++)
                av[i] = a[i];
            for(int k = 0; k < ver.size(); k++){
                jer += av[ver[k]];
                if((mask >> k)&1){
                    for(auto u : adj[ver[k]]){
                        av[ver[k]] += av[u];
                        av[u] = 0;
                    }
                }
            }
            for(int k = 0; k < ver.size(); k++)
                jer -= av[ver[k]];
            ans = max(ans, abs(jer));
        }
    }

    cout << ans << endl;
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:59:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(int k = 0; k < ver.size(); k++){
      |                            ~~^~~~~~~~~~~~
chase.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int k = 0; k < ver.size(); k++)
      |                            ~~^~~~~~~~~~~~

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