SHARE
TWEET

Untitled

a guest Nov 19th, 2019 63 in 343 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define     fRead           freopen("INPUT.txt","r",stdin)
  5. #define     fWrite          freopen("OUTPUT.txt","w",stdout)
  6. #define     ss(a)           scanf("%s",a)
  7. #define     gs(s)           getline(cin,s)
  8. #define     gc              getchar()
  9. #define     si(a)           scanf("%d",&a)
  10. #define     sii(a,b)        scanf("%d%d",&a,&b)
  11. #define     siii(a,b,c)     scanf("%d%d%d",&a,&b,&c)
  12. #define     sl(a)           scanf("%lld",&a)
  13. #define     sll(a,b)        scanf("%lld%lld",&a,&b)
  14. #define     slll(a,b,c)     scanf("%lld%lld%lld",&a,&b,&c)
  15. #define     sd(a)           scanf("%lf",&a)
  16. #define     sdd(a,b)        scanf("%lf%lf",&a,&b)
  17. #define     sddd(a,b,c)     scanf("%lf%lf%lf",&a,&b,&c)
  18. #define     deb(x)          cout << #x " = " <<(x) << endl
  19. #define     debb            printf("####\n")
  20. #define     pi(a)           printf("%d",a)
  21. #define     ps(a)           cout<<a
  22. #define     pl(a)           printf("%lld",a)
  23. #define     pd(a)           printf("%f",a)
  24. #define     pc(a)           printf("%c",a)
  25. #define     bl              printf("\n")
  26. #define     spc             printf(" ")
  27. #define     ll              long long
  28. #define     llu             unsigned long long
  29. #define     pie             2*acos(0.0)
  30. #define     eps             1e-9
  31. #define     qi              queue<int>
  32. #define     vi              vector<int>
  33. #define     vs              vector<string>
  34. #define     vd              vector<double>
  35. #define     vl              vector<long long>
  36. #define     pb              push_back
  37. #define     pii             pair <int,int>
  38. #define     mem(a,b)        memset(a,b,sizeof(a))
  39. #define     fl(i,a,n)       for(int i=a; i<n; i++)
  40. #define     rfl(i,n,a)      for(int i=n-1; i>=a; i--)
  41. #define     fit(x,mp)       for(auto x = mp.begin(); x!=mp.end(); x++)
  42. #define     MAX             20000 //10^6
  43. #define     inf             1000000000 //10^6
  44. #define     mod             1000000007
  45. int t, cs, n,a,b,w;
  46. int cost[MAX+5];
  47. int occ[MAX+5];
  48. int vis[MAX+5];
  49. vector<pii> v;
  50. vi ed[MAX+5];
  51. int dfs(int s)
  52. {
  53.     if(vis[s]) return occ[s];
  54.     vis[s] = occ[s] = 1;
  55.     fl(i,0,ed[s].size())
  56.         occ[s] += dfs(ed[s][i]);
  57.     return occ[s];
  58. }
  59. ll sum, ans;
  60. ll get(int I)
  61. {
  62.     ll oc = (ll)v[I].first;
  63.     ll val = (ll)v[I].second;
  64.     ll left = sum;
  65.     ll need = left/oc;
  66.     ll ret = 0;
  67.     if(need > val)
  68.     {
  69.         ret = val;
  70.     }
  71.     else
  72.     {
  73.         ret = need;
  74.         if(left%oc != 0 && val>need) ret++;
  75.     }
  76.     ans += ret;
  77.     return ret*oc;
  78. }
  79. int main()
  80. {
  81.     si(t);
  82.     while(t--)
  83.     {
  84.         si(n);
  85.         mem(cost,0);
  86.         mem(occ,0);
  87.         mem(vis,0);
  88.         fl(i,0,n+2) ed[i].clear();
  89.         fl(i,1,n)
  90.         {
  91.             siii(a,b,w);
  92.             ed[a].pb(b);
  93.             cost[b] = w;
  94.         }
  95.         sum = 0;
  96.         fl(i,1,n+1)
  97.         {
  98.             if(vis[i]==0)
  99.                 int x = dfs(i);
  100.         }
  101.         fl(i,1,n+1)
  102.         {
  103.             occ[i] = occ[i] * (n-occ[i]);
  104.             sum += occ[i]*cost[i];
  105.             if(cost[i]<0)
  106.                 v.pb(pii(occ[i],-cost[i]));
  107.         }
  108.         if(sum>=0)
  109.         {
  110.             printf("Case %d: 0\n",++cs);
  111.             continue;
  112.         }
  113.         sum = -sum;
  114.         ans = 0;
  115.         sort(v.begin(),v.end());
  116.         reverse(v.begin(),v.end());
  117.         fl(i,0,v.size())
  118.         {
  119.             if(sum<=0) break;
  120.             sum = sum - get(i);
  121.         }
  122.         printf("Case %d: %lld\n",++cs,ans);
  123.     }
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top