oj.uz

Submission #1028402

# Submission time Handle Problem Language Result Execution time Memory
1028402 2024-07-19T19:16:51 Z vjudge1 Chase (CEOI17_chase) C++17
70 / 100
 113 ms 93136 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using mii = map<ll,ll>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
const int N = 1e5 + 7,LOG=19;
vi graph[N];
ll n,V,p[N],pact[N],ans,act,dp[N][101],ady[N];
void dfsans(ll u,ll pa=0){
    if(pa==0)dp[u][1]=ady[u];
    else{
        fore(c,1,V+1){
            dp[u][c]=max(dp[pa][c],dp[pa][c-1]+ady[u]-p[pa]);
        }
    }
    fore(c,1,V+1)ans=max(ans,dp[u][c]);
    for(ll v:graph[u]){
        if(v==pa)continue;
        dfsans(v,u);
    }
}
void test_case(){
    cin >> n >> V;
    fo(i,n)cin>>p[i+1];
    fo(i,n-1){
        ll a,b;
        cin>>a>>b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    fore(i,1,n+1)
        for(int v:graph[i])
            ady[i]+=p[v];
    // dfs(1);
    for(ll a=1;a<=n;a++){
        if(n>1000&&a>1)break;
        act=-p[a];
        fore(i,1,n+1)pact[i]=p[i];
        fore(i,1,n+1)
            fo(j,101)
                dp[i][j]=0;
        dfsans(a);
    }
    cout<<ans<<endl;
}
int main(){cin.tie(0)->sync_with_stdio(0);
    int t=1;
    // cin >> t;
    while(t--)test_case();
}

Compilation message

chase.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
chase.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2808 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2808 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 77 ms 3648 KB Output is correct
8 Correct 35 ms 3672 KB Output is correct
9 Correct 27 ms 3676 KB Output is correct
10 Correct 84 ms 3676 KB Output is correct
11 Correct 48 ms 3676 KB Output is correct
12 Correct 35 ms 3924 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 91024 KB Output is correct
2 Correct 88 ms 93136 KB Output is correct
3 Correct 63 ms 90052 KB Output is correct
4 Correct 71 ms 90016 KB Output is correct
5 Correct 98 ms 89852 KB Output is correct
6 Correct 101 ms 90024 KB Output is correct
7 Correct 94 ms 89936 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2808 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 77 ms 3648 KB Output is correct
8 Correct 35 ms 3672 KB Output is correct
9 Correct 27 ms 3676 KB Output is correct
10 Correct 84 ms 3676 KB Output is correct
11 Correct 48 ms 3676 KB Output is correct
12 Correct 35 ms 3924 KB Output is correct
13 Correct 113 ms 91024 KB Output is correct
14 Correct 88 ms 93136 KB Output is correct
15 Correct 63 ms 90052 KB Output is correct
16 Correct 71 ms 90016 KB Output is correct
17 Correct 98 ms 89852 KB Output is correct
18 Correct 101 ms 90024 KB Output is correct
19 Correct 94 ms 89936 KB Output is correct
20 Incorrect 105 ms 89940 KB Output isn't correct
21 Halted 0 ms 0 KB -