Advertisement
yuhung94

E2

Nov 24th, 2022 (edited)
554
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 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,m){
  87.         if(e[i].k<=K){
  88.             v[e[i].f].eb(e[i].to);
  89.             v2[e[i].to].eb(e[i].f);
  90.         }
  91.     }
  92.     Kosaraju();
  93.     queue<int> Q;
  94.     rep(i,1,num){
  95.         L2[i]=L[i];
  96.         if(!d2[i]) Q.push(i);
  97.     }
  98.     while(Q.size()){
  99.         int x=Q.front();
  100.         Q.pop();
  101.         for(int i:v3[x]){
  102.             L2[i]=max(L2[i],L[i]+L2[x]);
  103.             d2[i]--;
  104.             if(!d2[i]) Q.push(i);
  105.         }
  106.     }
  107.     rep(i,1,n) ans+=L2[scc[i]];
  108.     return ans>=q;
  109. }
  110. signed main(){
  111.     quick
  112.     cin>>n>>m>>k>>q;
  113.     int Kmax=0;
  114.     rep(i,1,k) cin>>a[i];
  115.     rep(i,1,k) cin>>x[i];
  116.     rep(i,1,m){
  117.         cin>>e[i].f>>e[i].to>>e[i].k;
  118.         Kmax=max(Kmax,e[i].k);
  119.     }
  120.     rep(i,1,k){
  121.         val[a[i]]=x[i];
  122.     }
  123.     if(ok(0)) cout<<0<<"\n";
  124.     else if(!ok(Kmax)) cout<<"-1"<<"\n";
  125.     else{
  126.         int l=0;
  127.         int r=Kmax;
  128.         while(l+1<r){
  129.             int middle=(l+r)>>1;
  130.             if(ok(middle)) r=middle;
  131.             else l=middle;
  132.         }
  133.         cout<<r<<"\n";
  134.     }
  135.     return 0;
  136. }
  137.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement