Submission #469100

#TimeUsernameProblemLanguageResultExecution timeMemory
469100wdjpngOne-Way Streets (CEOI17_oneway)C++17
Compilation error
0 ms0 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2,avx,fma") #pragma GCC target ("native") #include <bits/stdc++.h> #define int long long #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; int n,v; vector<int>p; vector<vector<int>>mem; vector<vector<signed>>E; signed takei[100001][101]; signed notakei[100001][101]; int takemaxx[100001][101]; int notakemaxx[100001][101]; int takealtmaxx[100001][101]; int notakealtmaxx[100001][101]; int dfs(int pos, int bc, int parent) { if(parent!=-1&&mem[pos][bc]!=-1) return mem[pos][bc]; if(bc==0) return 0; int sum = 0; for(int w : E[pos]) { if(w==parent) continue; sum+=p[w]; } int maxx = 0; takemaxx[pos][bc]=0; takei[pos][bc] = -1; notakemaxx[pos][bc]=0; notakei[pos][bc] = -1; int t, nt; for(int w : E[pos]) { if(w==parent) continue; nt = dfs(w, bc, pos); t = dfs(w, bc-1, pos) + sum; if(nt>notakemaxx[pos][bc]) { notakei[pos][bc] = w; notakemaxx[pos][bc] = nt; } if(t>takemaxx[pos][bc]) { takei[pos][bc] = w; takemaxx[pos][bc] = t; } maxx=max(maxx, nt); maxx=max(maxx, t); } takealtmaxx[pos][bc] = 0; notakealtmaxx[pos][bc]=0; for(int w : E[pos]) { if(w==parent) continue; nt = dfs(w, bc, pos); t = dfs(w, bc-1, pos) + sum; if(takei[pos][bc]!=-1&&takei[pos][bc]!=w) { takealtmaxx[pos][bc]=max(takealtmaxx[pos][bc], t); } if(notakei[pos][bc]!=-1&&notakei[pos][bc]!=w) { notakealtmaxx[pos][bc]=max(notakealtmaxx[pos][bc], nt); } } return mem[pos][bc] = maxx; } int bruteforce() { int maxx=0; rep(i, n) { mem.assign(n+1, vector<int>(v+1, -1)); maxx=max(maxx, dfs(i+1, v, -1)); } return maxx; } int mx=0; void meta_dfs(int pos, int parent) { rep(i, v+1) mx = max(mx, dfs(pos, i, -1)); for(int w : E[pos]) { if(w==parent) continue; for(int i = 1; i<= v; i++) { mem[pos][i] = 0; if(takei[pos][i]!=w) mem[pos][i] = max(mem[pos][i], takemaxx[pos][i]-p[w]); else mem[pos][i] = max(mem[pos][i], takealtmaxx[pos][i]-p[w]); if(notakei[pos][i]!=w) mem[pos][i] = max(mem[pos][i], notakemaxx[pos][i]); else mem[pos][i] = max(mem[pos][i], notakealtmaxx[pos][i]); } meta_dfs(w,pos); } } // //void dfs2(int pos, int par) //{ // int sum = 0; // for(int w : E[pos]) // { // sum+=p[w]; // if(w!=par) dfs2(w,pos); // } // totsum[pos]=sum; //} signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>v; p.resize(n+1); rep(i, n) cin>>p[i+1]; E.resize(n+1); rep(i,n-1) { signed a,b; cin>>a>>b; E[a].push_back(b); E[b].push_back(a); } //dfs2(1,-1); //int maxx = dfs(1, v, -1); //if(n<=1000) maxx = bruteforce(); //cout<<maxx<<"\n"; mem.assign(n+1, vector<int>(v+1, -1)); meta_dfs(1, -1); cout<<mx<<"\n"; }

Compilation message (stderr)

cc1plus: error: attribute 'native' argument 'target' is unknown