Advertisement
yuhung94

E

Nov 24th, 2022 (edited)
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | None | 0 0
  1. #pragma GCC optimzize("Ofast,no-stack-protector")
  2. #include<bits/stdc++.h>
  3. #define int long long
  4. #define quick ios::sync_with_stdio(0);cin.tie(0);
  5. #define rep(x,a,b) for(int x=a;x<=b;x++)
  6. #define repd(x,a,b) for(int x=a;x>=b;x--)
  7. #define lowbit(x) (x&-x)
  8. #define sz(x) (int)(x.size())
  9. #define F first
  10. #define S second
  11. #define all(x) x.begin(),x.end()
  12. #define mp make_pair
  13. #define eb emplace_back
  14. using namespace std;
  15. typedef pair<int,int> pii;
  16. void debug(){
  17.     cout<<"\n";
  18. }
  19. template <class T,class ... U >
  20. void debug(T a, U ... b){
  21.     cout<<a<<" ",debug(b...);
  22. }
  23. const int N=1e6+7;
  24. const int INF=1e18;
  25. int n,m,q,k;
  26. vector<int> order;
  27. bool vis[N];
  28. int scc[N];
  29. vector<int> v[N];
  30. vector<int> v2[N];
  31. int num=0;
  32. int L[N];
  33. int val[N];
  34. int L2[N];
  35. int d2[N];
  36. vector<int> v3[N];
  37. void Revdfs(int x){
  38.     vis[x]=true;
  39.     for(int i:v2[x]){
  40.         if(!vis[i]){
  41.             Revdfs(i);
  42.         }
  43.     }
  44.     order.eb(x);
  45. }
  46. void dfs(int x){
  47.     scc[x]=num;
  48.     L[num]+=val[x];
  49.     for(int i:v[x]){
  50.         if(!scc[i]){
  51.             dfs(i);
  52.         }
  53.     }
  54. }
  55. void Kosaraju(){
  56.     num=0;
  57.     order.clear();
  58.     rep(i,1,n) vis[i]=false,L[i]=L2[i]=0,scc[i]=0,d2[i]=0;
  59.     rep(i,1,n){
  60.         if(!vis[i])Revdfs(i);
  61.     }
  62.     reverse(all(order));
  63.     for(int i:order){
  64.         if(!scc[i]) ++num,dfs(i);
  65.     }
  66.     rep(i,1,n){
  67.         for(int j:v[i]){
  68.             if(scc[j]!=scc[i]){
  69.                 v3[scc[j]].eb(scc[i]);
  70.                 d2[scc[i]]++;
  71.             }
  72.         }
  73.     }
  74.     //assert(num<=n);
  75. }
  76. struct edge{
  77.     int f,to,k;
  78. }e[N];
  79. int a[N];
  80. int x[N];
  81. bool ok(int K){
  82.     int ans=0;
  83.     /*fill(v,v+n+1,vector<int>());
  84.     fill(v2,v2+n+1,vector<int>());
  85.     fill(v3,v3+n+1,vector<int>());*/
  86.     rep(i,1,n) v[i].clear(),v2[i].clear(),v3[i].clear();
  87.     rep(i,1,m){
  88.         if(e[i].k<=K){
  89.             v[e[i].f].eb(e[i].to);
  90.             v2[e[i].to].eb(e[i].f);
  91.         }
  92.     }
  93.     Kosaraju();
  94.     queue<int> Q;
  95.     rep(i,1,num){
  96.         L2[i]=L[i];
  97.         if(!d2[i]) Q.push(i);
  98.     }
  99.     while(Q.size()){
  100.         int x=Q.front();
  101.         Q.pop();
  102.         for(int i:v3[x]){
  103.             L2[i]=max(L2[i],L[i]+L2[x]);
  104.             d2[i]--;
  105.             if(!d2[i]) Q.push(i);
  106.         }
  107.     }
  108.     rep(i,1,n) ans+=L2[scc[i]];
  109.     return ans>=q;
  110. }
  111. signed main(){
  112.     quick
  113.     cin>>n>>m>>k>>q;
  114.     int Kmax=0;
  115.     rep(i,1,k) cin>>a[i];
  116.     rep(i,1,k) cin>>x[i];
  117.     rep(i,1,m){
  118.         cin>>e[i].f>>e[i].to>>e[i].k;
  119.         Kmax=max(Kmax,e[i].k);
  120.     }
  121.     rep(i,1,k){
  122.         val[a[i]]=x[i];
  123.     }
  124.     if(ok(0)) cout<<0<<"\n";
  125.     else if(!ok(Kmax)) cout<<"-1"<<"\n";
  126.     else{
  127.         int l=0;
  128.         int r=Kmax;
  129.         while(l+1<r){
  130.             int middle=(l+r)>>1;
  131.             if(ok(middle)) r=middle;
  132.             else l=middle;
  133.         }
  134.         cout<<r<<"\n";
  135.     }
  136.     return 0;
  137. }
  138.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement