Submission #906181

#TimeUsernameProblemLanguageResultExecution timeMemory
9061818pete8Transport (COCI19_transport)C++17
0 / 130
1059 ms29260 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<float.h> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,ll> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound using namespace std; #define int long long #define double long double #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") const int mod=98765431,mxn=1e5,lg=22,inf=1e18,minf=-1e9,Mxn=100000; int val[mxn+10],n,sz[mxn+10],ans=0; vector<pii>adj[mxn+10]; bool del[mxn+10]; struct node{ int mnpref,sum,mnsuf; node operator+(node a)const{ node ans; ans.mnpref=min(mnpref,sum+a.mnpref); ans.mnsuf=min(a.mnsuf,a.sum+mnsuf); ans.sum=sum+a.sum; return ans; } }; node v[mxn+10]; void getsz(int cur,int p){ sz[cur]=1; for(auto i:adj[cur])if(i.f!=p&&!del[i.f])getsz(i.f,cur),sz[cur]+=sz[i.f]; } int getcen(int cur,int p,int mx){ for(auto i:adj[cur])if(i.f!=p&&!del[i.f]&&sz[i.f]>mx/2)return getcen(i.f,cur,mx); return cur; } int cnt=0; vector<int>deg[mxn+10]; int pos[mxn+10]; void solve(int cur,int p){ v[cur]=v[cur]+(node){val[cur],val[cur],val[cur]}; for(auto i:adj[cur]){ if(i.f!=p&&!del[i.f]){ v[i.f]=v[cur]+(node){-i.s,-i.s,-i.s}; solve(i.f,cur); } } deg[cnt].pb(cur); } struct fen{ int fwk[mxn+10]; void update(int pos,int val){for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;} int qry(int pos){ int sum=0; for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i]; return sum; } }t; bool cmp(pii a,pii b){return a.f<b.f;} void decomp(int cur){ getsz(cur,-1); int cen=getcen(cur,-1,sz[cur]); v[cen].mnpref=v[cen].mnsuf=v[cen].sum=val[cen]; for(auto i:adj[cen]){ if(del[i.f])continue; v[i.f]=v[cen]+(node){-i.s,-i.s,-i.s}; solve(i.f,cen); cnt++; }/* vector<pii>a; a.clear(); for(int i=0;i<cnt;i++)for(auto j:deg[i]){ if(v[j].mnpref>=0)ans++; if(v[j].mnsuf>=0)ans++; a.pb({-v[j].mnpref,j}); } sort(all(a)); //if sum+mnpref-val[node]>=0 sum-val[node]>=-mnpref for(int i=0;i<a.size();i++)pos[a[i].s]=i+1;*/ for(int i=0;i<cnt;i++){/* for(auto j:deg[i])t.update(pos[j],1); for(auto j:deg[i]){ if(v[j].mnsuf<0ll)continue; int it=ub(all(a),make_pair(v[j].sum-val[cen],inf),cmp)-a.begin()-1; if(it<0)continue; ans+=it+1-t.qry(it+1); } for(auto j:deg[i])t.update(pos[j],-1);*/ deg[i].clear(); } del[cen]=true; for(auto i:adj[cen])if(!del[i.f])decomp(i.f); } int32_t main(){ fastio cin>>n; for(int i=1;i<=n;i++)cin>>val[i]; for(int i=0;i<n-1;i++){ int a,b,w;cin>>a>>b>>w; adj[a].pb({b,w}); adj[b].pb({a,w}); } decomp(1); cout<<ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...