oj.uz

Submission #1028379

# Submission time Handle Problem Language Result Execution time Memory
1028379 2024-07-19T18:14:46 Z vjudge1 Chase (CEOI17_chase) C++17
0 / 100
 25 ms 12628 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<int>;
using ii = pair<int,int>;
using mii = map<int,int>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
const int N = 1e5 + 7,LOG=19;
vi graph[N];
int n,V,p[N],ni[N],up[N][LOG],pact[N];
ll ans,act;
void dfs(int u,int p=0){
    up[u][0]=p;
    fore(i,1,LOG)up[u][i]=up[up[u][i-1]][i-1];
    for(int v:graph[u]){
        if(v==p)continue;
        ni[v]=ni[u]+1;
        dfs(v,u);
    }
}
int LCA(int a, int b){
    if(ni[a]<ni[b])swap(a,b);
    ffo(i,LOG)a=(ni[up[a][i]]>=ni[b]?up[a][i]:a);
    ffo(i,LOG)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
    return (a==b?a:up[a][0]);
}
void dfsans(int u,int d=1,int p=0){
    deque<int> mem;
    for(int v:graph[u])mem.pb(pact[v]),pact[u]+=pact[v],pact[v]=0;
    // cout<<u<<" "<<d<<" "<<p<<" "<<act<<" "<<pact[u]<<endl;
    // si jerry se sale en este momento
    ans=max(ans,pact[u]+act);
    for(int v:graph[u]){
        if(v==p||d==V)continue;
        dfsans(v,d+1,u);
    }
    //rollback
    for(int v:graph[u])pact[u]-=mem.front(),pact[v]=mem.front(),mem.pop_front();
}
void test_case(){
    cin >> n >> V;
    fo(i,n)cin>>p[i+1];
    fo(i,n-1){
        int a,b;
        cin>>a>>b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    // dfs(1);
    for(int a=1;a<=n;a++){
        if(n>1000&&a>1)break;
        act=-p[a];
        fore(i,1,n+1)pact[i]=p[i];
        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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 12628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -