Submission #265037

#TimeUsernameProblemLanguageResultExecution timeMemory
265037GoolakhElection Campaign (JOI15_election_campaign)C++17
100 / 100
434 ms40824 KiB
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O2") #define F first #define S second #define pb push_back #define SZ(x) (ll)(x.size()) #define all(x) x.begin(),x.end() #define MP make_pair typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=1e5+10, maxm=1e6+10, lg=17, mod=1e9+7, inf=1e18; #define git(x) (x&-x) ll n,m,A[maxn],B[maxn],C[maxn],par[maxn][lg+1],ss[maxn][lg+1],st[maxn],ft[maxn],tt,h[maxn],bit[maxn],dp[maxn]; vector<ll> g[maxn],Q[maxn]; void add(ll i,ll x){for(;i<maxn;i+=git(i))bit[i]+=x;} ll get(ll i){ll ret=0;for(;i;i-=git(i))ret+=bit[i];return ret;} void pfs(ll v=1,ll p=0){ st[v]=++tt; h[v]=h[par[v][0]=p]+1; for(int i=1;i<=lg;i++) par[v][i]=par[par[v][i-1]][i-1]; for(auto u:g[v])if(u!=p) pfs(u,v); ft[v]=tt+1; } ll parx(ll v,ll x){ if(x<=0) return v; for(int i=0;i<=lg;i++)if(x>>i&1) v=par[v][i]; return v; } ll lca(ll v,ll u){ if(h[v]<h[u]) swap(v,u); v=parx(v,h[v]-h[u]); if(v==u) return v; for(int i=lg;i>=0;i--)if(par[v][i]!=par[u][i]) v=par[v][i], u=par[u][i]; return par[v][0]; } void dfs(ll v=1,ll p=0){ ll bac=0; for(auto u:g[v])if(u!=p) dfs(u,v), bac+=dp[u]; dp[v]=bac; for(auto i:Q[v]) dp[v]=max(dp[v],C[i]+bac+get(st[A[i]])+get(st[B[i]])); //cout<<v<<' '<<dp[v]<<endl; add(st[v],bac-dp[v]); add(ft[v],-(bac-dp[v])); } int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<n;i++){ ll v,u; cin>>v>>u; g[v].pb(u), g[u].pb(v); } pfs(); cin>>m; for(int i=0;i<m;i++) cin>>A[i]>>B[i]>>C[i], Q[lca(A[i],B[i])].pb(i); dfs(); cout<<dp[1]; return 0; } // a denial a denial a denial a denial a denial a denial
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...