Advertisement
updown

Untitled

Mar 18th, 2023
650
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define For(i, a, b) for(int i=a; i<b; i++)
  5. #define ffi For(i, 0, N)
  6. #define ffj For(j, 0, N)
  7. #define ffa ffi ffj
  8. #define s <<" "<<
  9. #define c <<" : "<<
  10. #define w cout
  11. #define e "\n"
  12. #define pb push_back
  13. #define mp make_pair
  14. #define a first
  15. #define b second
  16. #define int ll
  17. //500,000,000 operations
  18. const int MAXN = 1500, MOD=1000000007;
  19. //Global Variables
  20. int N, M, X, Y, cnt[MAXN][2501], tree[MAXN], N2, sum[MAXN], dp_old[2501], sum_old, dp[2501], nsum;
  21. vector<pair<int, int> > adj[MAXN];
  22.  
  23. void go_tree(int at) {
  24.     if (tree[at] != -1) return;
  25.     tree[at] = N2;
  26.     for (auto i: adj[at]) go_tree(i.a);
  27. }
  28. void get_len(int at, int d, int p, bool good=true) {
  29.     if (good) {
  30.         if (d < Y) cnt[tree[at]][d]++;
  31.         else {
  32.             cnt[tree[at]][Y]++;
  33.             sum[tree[at]] += d;
  34.         }
  35.     }
  36.     for (auto i: adj[at]) if (i.a != p) get_len(i.a, d+i.b, at);
  37. }
  38.  
  39. main() {
  40.     //ifstream cin ("test.in");
  41.     ifstream cin("mooriokart.in"); ofstream cout("mooriokart.out");
  42.     ios_base::sync_with_stdio; cin.tie(0);
  43.     cin >> N >> M >> X >> Y;
  44.     Y = Y-(N-M)*X; Y = max(Y, (int)0);
  45.     For (j, 0, M) {int a, b, d; cin >> a >> b >> d; a--; b--; adj[a].pb(mp(b, d)); adj[b].pb(mp(a, d));}
  46.     ffi tree[i] = -1;
  47.     ffi if (tree[i] == -1) {go_tree(i); N2++;} /// floodfill trees
  48.     ffi {
  49.         /// start at node i
  50.         get_len(i, 0, -1, false);
  51.     }
  52.     sum[0] /= 2; For (j, 0, Y+1) cnt[0][j] /= 2; /// every path should only be counted once
  53.     For (i, 0, N2) sum[i] %= MOD;
  54.     //For (i, 0, N2) {w<< "i:" s i+1 c sum[i]<<e; For (j, 0, 10) if (cnt[i][j] != 0) w<< j s cnt[i][j]<<e;}
  55.     For (i, 0, Y+1) dp[i] = cnt[0][i]; nsum = sum[0];
  56.     For (j, 1, N2) {
  57.         /// move to old
  58.         For (i, 0, Y+1) {dp_old[i] = dp[i]; dp[i] = 0;} sum_old = nsum; nsum = 0;
  59.         /// knapsack
  60.         For (i, 0, Y) if (cnt[j][i] != 0) For (p, 0, Y) if (dp_old[p] != 0) {
  61.             /// combine i & p
  62.             if (i+p < Y) {
  63.                 dp[i+p] += cnt[j][i]*dp_old[p];
  64.                 dp[i+p] %= MOD;
  65.             }
  66.             else {
  67.                 dp[Y] += cnt[j][i]*dp_old[p];
  68.                 dp[Y] %= MOD;
  69.                 nsum += dp_old[p]*cnt[j][i]*(i+p);
  70.                 nsum %= MOD;
  71.             }
  72.         }
  73.         /// previous N-1 >= Y
  74.         For (p, 0, Y) {
  75.             dp[Y] += dp_old[Y]*cnt[j][p];
  76.             dp[Y] %= MOD;
  77.             nsum += cnt[j][p]*p*dp_old[Y] + sum_old*cnt[j][p];
  78.             nsum %= MOD;
  79.         }
  80.         /// current >= Y
  81.         For (i, 0, Y) {
  82.             dp[Y] += cnt[j][Y]*dp_old[i];
  83.             dp[Y] %= MOD;
  84.             nsum += dp_old[i]*i*cnt[j][Y] + sum[j]*dp_old[i];
  85.             nsum %= MOD;
  86.         }
  87.         /// i = p = Y
  88.         dp[Y] += cnt[j][Y]*dp_old[Y];
  89.         dp[Y] %= MOD;
  90.         nsum += sum_old*cnt[j][Y] + sum[j]*dp_old[Y];
  91.         nsum %= MOD;
  92.     }
  93.     //w<< nsum s dp[Y]<<e;
  94.     nsum += X*(N-M)*dp[Y];
  95.     assert(nsum >= 0);
  96.     nsum %= MOD;
  97.     //w<< nsum<<e;
  98.     int mul = N-M-1;
  99.     For (i, 1, mul+1) {
  100.         nsum *= i;
  101.         nsum %= MOD;
  102.     }
  103.     w<< nsum<<e;
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement