oj.uz

Submission #561236

# Submission time Handle Problem Language Result Execution time Memory
561236 2022-05-12T13:52:03 Z fatemetmhr Chase (CEOI17_chase) C++17
20 / 100
 4000 ms 9944 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Execution timed out 4064 ms 2700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4019 ms 9944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 6 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Execution timed out 4064 ms 2700 KB Time limit exceeded
8 Halted 0 ms 0 KB -