oj.uz

Submission #769357

# Submission time Handle Problem Language Result Execution time Memory
769357 2023-06-29T12:57:03 Z peijar Two Currencies (JOI23_currencies) C++17
100 / 100
 974 ms 50136 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

const int MAXN = 1e5;
const int MAXP = 17;

int par[MAXP][MAXN];
vector<int> adj[MAXN];
int depth[MAXN], tin[MAXN], tout[MAXN];
int T;

void dfs(int u, int p) {
  tin[u] = T++;
  par[0][u] = p;
  for (int i = 0; i < MAXP - 1; ++i)
    par[i + 1][u] = par[i][par[i][u]];
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
  tout[u] = T++;
}

int getLca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  int diff = depth[u] - depth[v];
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & diff)
      u = par[p][u];
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p)
    if (par[p][u] != par[p][v])
      u = par[p][u], v = par[p][v];

  return par[0][u];
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbPoids, nbRequetes;
  cin >> nbSommets >> nbPoids >> nbRequetes;

  vector<pair<int, int>> edges(nbSommets - 1);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(0, 0);
  vector<pair<int, int>> weights(nbPoids);
  for (int i = 0; i < nbPoids; ++i) {
    int p, c;
    cin >> p >> c;
    --p;
    auto [u, v] = edges[p];
    if (depth[u] > depth[v])
      swap(u, v);
    weights[i] = pair(c, v);
  }
  sort(weights.begin(), weights.end());

  vector<tuple<int, int, int, int>> queries(nbRequetes);
  for (auto &[s, t, gold, silver] : queries) {
    cin >> s >> t >> gold >> silver;
    --s, --t;
    if (tin[s] > tin[t])
      swap(s, t);
  }
  dbg(nbSommets, nbPoids, nbRequetes);
  vector<int> lca(nbRequetes);
  for (int i = 0; i < nbRequetes; ++i) {
    auto [s, t, gold, silver] = queries[i];
    lca[i] = getLca(s, t);
    dbg(s, t, lca[i]);
  }

  vector<int> lo(nbRequetes), up(nbRequetes, nbPoids);
  vector<int> cntFinal(nbRequetes, 1e18);
  vector<int> cntTotal(nbRequetes);

  while (true) {
    bool change = false;
    vector<vector<int>> needCheck(nbPoids + 1);
    for (int i = 0; i < nbRequetes; ++i) {
      if (lo[i] < up[i]) {
        int mid = (lo[i] + up[i] + 1) / 2;
        change = true;
        needCheck[mid].push_back(i);
      } else
        needCheck[lo[i]].push_back(i);
    }

    Fenwick<int> fenCnt(T), fenSum(T);

    for (int iPoids = 0; iPoids <= nbPoids; ++iPoids) {
      for (int iRequete : needCheck[iPoids]) {
        int l = lca[iRequete];
        auto [u, v, gold, silver] = queries[iRequete];
        int cnt = fenCnt.sum(tin[u] + 1) + fenCnt.sum(tin[v] + 1) -
                  2 * fenCnt.sum(tin[l] + 1);
        int sum = fenSum.sum(tin[u] + 1) + fenSum.sum(tin[v] + 1) -
                  2 * fenSum.sum(tin[l] + 1);
        cntFinal[iRequete] = cnt;
        if (sum <= silver)
          lo[iRequete] = iPoids;
        else
          up[iRequete] = iPoids - 1;
      }

      if (iPoids < nbPoids) {
        auto [c, u] = weights[iPoids];
        fenCnt.upd(tin[u], 1);
        fenCnt.upd(tout[u], -1);
        fenSum.upd(tin[u], c);
        fenSum.upd(tout[u], -c);
      }
    }
    for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
      int l = lca[iRequete];
      auto [u, v, gold, silver] = queries[iRequete];
      int cnt = fenCnt.sum(tin[u] + 1) + fenCnt.sum(tin[v] + 1) -
                2 * fenCnt.sum(tin[l] + 1);
      cntTotal[iRequete] = cnt;
    }
    if (!change)
      break;
  }
  for (int i = 0; i < nbRequetes; ++i) {
    auto [u, v, gold, silver] = queries[i];
    dbg(cntFinal[i], cntTotal[i]);
    cout << max(-1LL, gold - (cntTotal[i] - cntFinal[i])) << endl;
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 7 ms 3412 KB Output is correct
6 Correct 9 ms 3540 KB Output is correct
7 Correct 9 ms 3336 KB Output is correct
8 Correct 10 ms 3584 KB Output is correct
9 Correct 9 ms 3592 KB Output is correct
10 Correct 11 ms 3608 KB Output is correct
11 Correct 10 ms 3504 KB Output is correct
12 Correct 10 ms 3588 KB Output is correct
13 Correct 11 ms 3760 KB Output is correct
14 Correct 9 ms 3668 KB Output is correct
15 Correct 9 ms 3600 KB Output is correct
16 Correct 9 ms 3652 KB Output is correct
17 Correct 9 ms 3580 KB Output is correct
18 Correct 9 ms 3592 KB Output is correct
19 Correct 8 ms 3632 KB Output is correct
20 Correct 8 ms 3540 KB Output is correct
21 Correct 8 ms 3596 KB Output is correct
22 Correct 8 ms 3540 KB Output is correct
23 Correct 8 ms 3536 KB Output is correct
24 Correct 9 ms 3616 KB Output is correct
25 Correct 9 ms 3628 KB Output is correct
26 Correct 7 ms 3540 KB Output is correct
27 Correct 7 ms 3540 KB Output is correct
28 Correct 7 ms 3540 KB Output is correct
29 Correct 7 ms 3592 KB Output is correct
30 Correct 11 ms 3616 KB Output is correct
31 Correct 9 ms 3540 KB Output is correct
32 Correct 11 ms 3588 KB Output is correct
33 Correct 9 ms 3636 KB Output is correct
34 Correct 9 ms 3668 KB Output is correct
35 Correct 9 ms 3708 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 9 ms 3616 KB Output is correct
3 Correct 9 ms 3540 KB Output is correct
4 Correct 9 ms 3540 KB Output is correct
5 Correct 536 ms 40264 KB Output is correct
6 Correct 667 ms 36016 KB Output is correct
7 Correct 598 ms 37876 KB Output is correct
8 Correct 481 ms 35692 KB Output is correct
9 Correct 462 ms 35296 KB Output is correct
10 Correct 782 ms 44664 KB Output is correct
11 Correct 769 ms 44652 KB Output is correct
12 Correct 728 ms 44680 KB Output is correct
13 Correct 750 ms 44640 KB Output is correct
14 Correct 773 ms 44692 KB Output is correct
15 Correct 812 ms 49668 KB Output is correct
16 Correct 779 ms 50068 KB Output is correct
17 Correct 751 ms 49380 KB Output is correct
18 Correct 849 ms 44676 KB Output is correct
19 Correct 888 ms 44632 KB Output is correct
20 Correct 880 ms 44644 KB Output is correct
21 Correct 690 ms 44496 KB Output is correct
22 Correct 718 ms 44708 KB Output is correct
23 Correct 698 ms 44832 KB Output is correct
24 Correct 718 ms 44724 KB Output is correct
25 Correct 692 ms 45440 KB Output is correct
26 Correct 799 ms 45216 KB Output is correct
27 Correct 591 ms 45396 KB Output is correct
28 Correct 490 ms 44376 KB Output is correct
29 Correct 433 ms 44364 KB Output is correct
30 Correct 554 ms 44636 KB Output is correct
31 Correct 582 ms 45008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 9 ms 3700 KB Output is correct
3 Correct 9 ms 3668 KB Output is correct
4 Correct 9 ms 3656 KB Output is correct
5 Correct 501 ms 42292 KB Output is correct
6 Correct 459 ms 41000 KB Output is correct
7 Correct 624 ms 35140 KB Output is correct
8 Correct 945 ms 50000 KB Output is correct
9 Correct 963 ms 50136 KB Output is correct
10 Correct 859 ms 50040 KB Output is correct
11 Correct 721 ms 50020 KB Output is correct
12 Correct 730 ms 50012 KB Output is correct
13 Correct 665 ms 50056 KB Output is correct
14 Correct 570 ms 49652 KB Output is correct
15 Correct 577 ms 49444 KB Output is correct
16 Correct 730 ms 49692 KB Output is correct
17 Correct 644 ms 49652 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 7 ms 3412 KB Output is correct
6 Correct 9 ms 3540 KB Output is correct
7 Correct 9 ms 3336 KB Output is correct
8 Correct 10 ms 3584 KB Output is correct
9 Correct 9 ms 3592 KB Output is correct
10 Correct 11 ms 3608 KB Output is correct
11 Correct 10 ms 3504 KB Output is correct
12 Correct 10 ms 3588 KB Output is correct
13 Correct 11 ms 3760 KB Output is correct
14 Correct 9 ms 3668 KB Output is correct
15 Correct 9 ms 3600 KB Output is correct
16 Correct 9 ms 3652 KB Output is correct
17 Correct 9 ms 3580 KB Output is correct
18 Correct 9 ms 3592 KB Output is correct
19 Correct 8 ms 3632 KB Output is correct
20 Correct 8 ms 3540 KB Output is correct
21 Correct 8 ms 3596 KB Output is correct
22 Correct 8 ms 3540 KB Output is correct
23 Correct 8 ms 3536 KB Output is correct
24 Correct 9 ms 3616 KB Output is correct
25 Correct 9 ms 3628 KB Output is correct
26 Correct 7 ms 3540 KB Output is correct
27 Correct 7 ms 3540 KB Output is correct
28 Correct 7 ms 3540 KB Output is correct
29 Correct 7 ms 3592 KB Output is correct
30 Correct 11 ms 3616 KB Output is correct
31 Correct 9 ms 3540 KB Output is correct
32 Correct 11 ms 3588 KB Output is correct
33 Correct 9 ms 3636 KB Output is correct
34 Correct 9 ms 3668 KB Output is correct
35 Correct 9 ms 3708 KB Output is correct
36 Correct 1 ms 2772 KB Output is correct
37 Correct 9 ms 3616 KB Output is correct
38 Correct 9 ms 3540 KB Output is correct
39 Correct 9 ms 3540 KB Output is correct
40 Correct 536 ms 40264 KB Output is correct
41 Correct 667 ms 36016 KB Output is correct
42 Correct 598 ms 37876 KB Output is correct
43 Correct 481 ms 35692 KB Output is correct
44 Correct 462 ms 35296 KB Output is correct
45 Correct 782 ms 44664 KB Output is correct
46 Correct 769 ms 44652 KB Output is correct
47 Correct 728 ms 44680 KB Output is correct
48 Correct 750 ms 44640 KB Output is correct
49 Correct 773 ms 44692 KB Output is correct
50 Correct 812 ms 49668 KB Output is correct
51 Correct 779 ms 50068 KB Output is correct
52 Correct 751 ms 49380 KB Output is correct
53 Correct 849 ms 44676 KB Output is correct
54 Correct 888 ms 44632 KB Output is correct
55 Correct 880 ms 44644 KB Output is correct
56 Correct 690 ms 44496 KB Output is correct
57 Correct 718 ms 44708 KB Output is correct
58 Correct 698 ms 44832 KB Output is correct
59 Correct 718 ms 44724 KB Output is correct
60 Correct 692 ms 45440 KB Output is correct
61 Correct 799 ms 45216 KB Output is correct
62 Correct 591 ms 45396 KB Output is correct
63 Correct 490 ms 44376 KB Output is correct
64 Correct 433 ms 44364 KB Output is correct
65 Correct 554 ms 44636 KB Output is correct
66 Correct 582 ms 45008 KB Output is correct
67 Correct 2 ms 2772 KB Output is correct
68 Correct 9 ms 3700 KB Output is correct
69 Correct 9 ms 3668 KB Output is correct
70 Correct 9 ms 3656 KB Output is correct
71 Correct 501 ms 42292 KB Output is correct
72 Correct 459 ms 41000 KB Output is correct
73 Correct 624 ms 35140 KB Output is correct
74 Correct 945 ms 50000 KB Output is correct
75 Correct 963 ms 50136 KB Output is correct
76 Correct 859 ms 50040 KB Output is correct
77 Correct 721 ms 50020 KB Output is correct
78 Correct 730 ms 50012 KB Output is correct
79 Correct 665 ms 50056 KB Output is correct
80 Correct 570 ms 49652 KB Output is correct
81 Correct 577 ms 49444 KB Output is correct
82 Correct 730 ms 49692 KB Output is correct
83 Correct 644 ms 49652 KB Output is correct
84 Correct 542 ms 36816 KB Output is correct
85 Correct 520 ms 30256 KB Output is correct
86 Correct 531 ms 28656 KB Output is correct
87 Correct 838 ms 44580 KB Output is correct
88 Correct 882 ms 44648 KB Output is correct
89 Correct 917 ms 44544 KB Output is correct
90 Correct 974 ms 44592 KB Output is correct
91 Correct 843 ms 44660 KB Output is correct
92 Correct 840 ms 48320 KB Output is correct
93 Correct 847 ms 49336 KB Output is correct
94 Correct 943 ms 44612 KB Output is correct
95 Correct 880 ms 44720 KB Output is correct
96 Correct 877 ms 44744 KB Output is correct
97 Correct 886 ms 44620 KB Output is correct
98 Correct 782 ms 44740 KB Output is correct
99 Correct 844 ms 44644 KB Output is correct
100 Correct 786 ms 44692 KB Output is correct
101 Correct 822 ms 44776 KB Output is correct
102 Correct 752 ms 45220 KB Output is correct
103 Correct 740 ms 45296 KB Output is correct
104 Correct 837 ms 45204 KB Output is correct
105 Correct 648 ms 44556 KB Output is correct
106 Correct 570 ms 44696 KB Output is correct
107 Correct 585 ms 44408 KB Output is correct
108 Correct 536 ms 44444 KB Output is correct