Submission #1035116

#TimeUsernameProblemLanguageResultExecution timeMemory
1035116BABY_GANGSTERJobs (BOI24_jobs)C++14
14 / 100
136 ms38992 KiB
//https://www.instagram.com/_modwwe/ #pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2") #include<bits/stdc++.h> #define int long long //#define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void phongbeo(); const int inf=1e18; const int mod2=1e9+7; const int mod1=998244353; struct icd { int a,b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c,d,e,f; }; int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l,s33; int i,s10,s12; int kk; int el=29; main() { #ifndef ONLINE_JUDGE // fin(task),fou(task); #endif ///NHP /// cin>>s1; // modwwe phongbeo(); } vector<ib> v[300001]; struct cmp { bool operator()(ib a,ib b) { return a.a>b.a; } }; priority_queue<ib,vector<ib>,cmp>p; int heavy[100001]; int a[100001]; bool b[100001]; bool cmp2(ib a,ib b) { return a.b>b.b; } int dfs(int x,int c,int d,int e) { int d2=c-d; int e2=e; vector<ib> vv; for(auto f:v[x]) { if(c>=0) d=c,e=0; vv.pb({f.a,dfs(f.a,c+f.b,d,min(c-d,e))}); } sort(vv.begin(),vv.end(),cmp2); if(vv.size()!=0)heavy[x]=vv[0].a; if(c-d>=0) return e2; else if(vv.size()!=0) return vv[0].b; else return -1e18; } void dfs2(int x,int y,int e,int d,int g) { b[x]=1; //cout<<x<<" "<<g<<" "<<heavy[x]<<" "<<e<<" "<<d,debug if(d>=0)p.push({abs(e),d}),d=0,e=0,y=0; if(heavy[x]!=0)dfs2(heavy[x],y,min(e,d-y),d+a[heavy[x]],g); for(auto f:v[x]) if(!b[f.a]) dfs2(f.a,0,min(0ll,a[f.a]),a[f.a],x); } void phongbeo() { cin>>n>>dem; dem2=dem; for(int i=1;i<=n;i++) cin>>l>>r,v[r].pb({i,l}),a[i]=l; dfs(0,0,0,0); dfs2(0,0,0,0,0); while(!p.empty()) { ib x=p.top(); if(dem>=x.a)dem+=x.b; else break; p.pop(); } cout<<dem-dem2; }

Compilation message (stderr)

Main.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
Main.cpp: In function 'long long int dfs(long long int, long long int, long long int, long long int)':
Main.cpp:77:5: warning: unused variable 'd2' [-Wunused-variable]
   77 | int d2=c-d;
      |     ^~
#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...