oj.uz

답안 #727530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727530 2023-04-21T00:03:28 Z cig32 Two Currencies (JOI23_currencies) C++17
100 / 100
 3267 ms 173988 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int mxs = 1e14;
int32_t n, m, q;
vector<int> adj[MAXN];
int st[MAXN], en[MAXN], cur = 0;
bool is[MAXN];
int cost[MAXN];
pair<int,int> anc[19][2*MAXN];
int dep[MAXN];
vector<int> euler;
int dfn[2*MAXN];
void dfs(int node, int prv) {
  st[node] = ++cur;
  dfn[cur] = node;
  euler.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  for(int x: adj[node]) {
    if(x != prv) {
      dfs(x, node);
      euler.push_back(node);
    }
  }
  en[node] = ++cur;
  dfn[cur] = node;
}
int ans[MAXN];
int block;
int32_t s[MAXN], t[MAXN], x[MAXN];
int y[MAXN], p[MAXN]; //lca
int mi[MAXN], ma[MAXN], ord[MAXN];
int l[MAXN], r[MAXN];
int lca(int u, int v) {
  int m1 = min(mi[u], mi[v]), m2 = max(ma[u], ma[v]);
  int k = 32 - __builtin_clz(m2-m1+1) - 1;
  return min(anc[k][m1], anc[k][m2 - (1<<k) + 1]).second;
}
bool cmp(int qa, int qb) {
  if(l[qa] / block != l[qb] / block) return l[qa] / block < l[qb] / block;
  return r[qa] < r[qb];
}
pair<int,int> chkpt[MAXN];
int freq[MAXN];
int pos[MAXN];
int val[MAXN];
int sumblock[MAXN];
int cnt[MAXN];
inline void ins(int x) {
  int pp = pos[x];
  val[pp] = cost[x];
  cnt[pp / block]++;
  sumblock[pp / block] += cost[x];
}
inline void del(int x) {
  int pp = pos[x];
  val[pp] = 0;
  cnt[pp / block]--;
  sumblock[pp / block] -= cost[x];
}
inline void add(int x) {
  x = dfn[x];
  if(!is[x]) return;
  freq[x]++;
  if(freq[x] == 2) del(x);
  else ins(x);
}
inline void sub(int x) {
  x = dfn[x];
  if(!is[x]) return;
  freq[x]--;
  if(freq[x] == 0) del(x);
  else ins(x);
}
pair<int,int> sto[MAXN];
vector<int> stuff[MAXN];
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long x, long long y) {
  long long u = uniform_int_distribution<long long>(x, y)(rng);
  return u;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  scanf("%d %d %d", &n, &m, &q);
  for(int i=0; i+1<n; i++) {
    int32_t u, v;
    scanf("%d %d", &u, &v);
    sto[i] = {u, v};
  }
  int rt = rnd(1, n);
  for(int i=0; i<m; i++) {
    int32_t p, c;
    scanf("%d %d", &p, &c);
    n++;
    p--;
    stuff[p].push_back(n);
    is[n] = 1;
    cost[n] = c;
    chkpt[i] = {c, n};
  }
  for(int i=0; i+1<n-m; i++) {
    int u = sto[i].first;
    int v = sto[i].second;
    if(stuff[i].empty()) {
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    else {
      adj[u].push_back(stuff[i][0]);
      adj[stuff[i][0]].push_back(u);
      for(int j=0; j+1<stuff[i].size(); j++) {
        adj[stuff[i][j]].push_back(stuff[i][j+1]);
        adj[stuff[i][j+1]].push_back(stuff[i][j]);
      }
      int fin = stuff[i].size() - 1;
      adj[stuff[i][fin]].push_back(v);
      adj[v].push_back(stuff[i][fin]);
    }
  }
  block = ceil(sqrt(n)) * 2;
  sort(chkpt, chkpt + m);
  for(int i=0; i<m; i++) pos[chkpt[i].second] = i;
  dfs(rt, -1);
  for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
  for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
  for(int i=euler.size()-1; i>=0; i--) mi[euler[i]] = i;
  for(int i=1; i<19; i++) {
    for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      anc[i][j] = min(anc[i-1][j], anc[i-1][j+(1<<(i-1))]);
    }
  }
  for(int i=1; i<=q; i++) {
    scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
    if(st[s[i]] > st[t[i]]) swap(s[i], t[i]);
    p[i] = lca(s[i], t[i]);
    if(s[i] == p[i]) l[i] = st[s[i]], r[i] = st[t[i]];
    else l[i] = en[s[i]], r[i] = st[t[i]];
  }
  for(int i=1; i<=q; i++) ord[i] = i;
  sort(ord+1, ord+q+1, cmp);
  block = ceil(sqrt(m));
  int lprev = 0, rprev = 0;
  for(int i=1; i<=q; i++) {
    int idx = ord[i];
    int lnew = l[idx], rnew = r[idx];
    while(rprev < rnew) {
      rprev++; add(rprev);
    }
    while(lprev > lnew) {
      lprev--; add(lprev);
    }
    while(rprev > rnew) {
      sub(rprev); rprev--;
    }
    while(lprev < lnew) {
      sub(lprev); lprev++;
    }
    int run = 0; // number of checkpoints payable using silver
    int gold = x[idx], silver = y[idx];
    if(silver >= mxs) {
      ans[idx] = gold;
      continue;
    }
    int tcc = 0;
    bool pk = 0;
    for(int j=0; j<block; j++) {
      tcc += cnt[j];
      if(pk)continue;
      if(sumblock[j] <= silver) {
        silver -= sumblock[j];
        run += cnt[j];
      }
      else { 
        int mlm = min((int) m, (j+1) * block);
        for(int k=j*block; k<mlm; k++) {
          if(val[k] <= silver && val[k] > 0) {
            silver -= val[k];
            run++;
          }
        }
        pk = 1;
      }
    }
    gold -= (tcc - run);
    gold = max(gold, -1ll);
    ans[idx] = gold;
  }
  for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}
/*
4 6 1
1 2
2 3
1 4
2 1
4 1
3 5
3 2
4 2
3 2
1 4 2 6
*/

Compilation message

currencies.cpp: In function 'int32_t main()':
currencies.cpp:115:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       for(int j=0; j+1<stuff[i].size(); j++) {
      |                    ~~~^~~~~~~~~~~~~~~~
currencies.cpp:128:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
      |                ~^~~~~~~~~~~~~
currencies.cpp:129:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
      |                ~^~~~~~~~~~~~~
currencies.cpp:132:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~
currencies.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d %d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d %d", &p, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9900 KB Output is correct
5 Correct 13 ms 12076 KB Output is correct
6 Correct 14 ms 12228 KB Output is correct
7 Correct 12 ms 11556 KB Output is correct
8 Correct 16 ms 12328 KB Output is correct
9 Correct 17 ms 12244 KB Output is correct
10 Correct 15 ms 12244 KB Output is correct
11 Correct 14 ms 12332 KB Output is correct
12 Correct 14 ms 12244 KB Output is correct
13 Correct 15 ms 12452 KB Output is correct
14 Correct 15 ms 12448 KB Output is correct
15 Correct 13 ms 12360 KB Output is correct
16 Correct 16 ms 12392 KB Output is correct
17 Correct 14 ms 12328 KB Output is correct
18 Correct 16 ms 12324 KB Output is correct
19 Correct 15 ms 12244 KB Output is correct
20 Correct 13 ms 12328 KB Output is correct
21 Correct 14 ms 12320 KB Output is correct
22 Correct 14 ms 12244 KB Output is correct
23 Correct 12 ms 12320 KB Output is correct
24 Correct 11 ms 12320 KB Output is correct
25 Correct 11 ms 12372 KB Output is correct
26 Correct 10 ms 12244 KB Output is correct
27 Correct 9 ms 12328 KB Output is correct
28 Correct 12 ms 12272 KB Output is correct
29 Correct 13 ms 12332 KB Output is correct
30 Correct 17 ms 12324 KB Output is correct
31 Correct 15 ms 12336 KB Output is correct
32 Correct 14 ms 12244 KB Output is correct
33 Correct 12 ms 12408 KB Output is correct
34 Correct 13 ms 12456 KB Output is correct
35 Correct 11 ms 12452 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 17 ms 12228 KB Output is correct
3 Correct 15 ms 12316 KB Output is correct
4 Correct 17 ms 12244 KB Output is correct
5 Correct 2424 ms 150540 KB Output is correct
6 Correct 2029 ms 123168 KB Output is correct
7 Correct 1724 ms 121380 KB Output is correct
8 Correct 1529 ms 119968 KB Output is correct
9 Correct 1646 ms 123348 KB Output is correct
10 Correct 2769 ms 161492 KB Output is correct
11 Correct 2726 ms 161520 KB Output is correct
12 Correct 2771 ms 161524 KB Output is correct
13 Correct 2926 ms 161628 KB Output is correct
14 Correct 3103 ms 161504 KB Output is correct
15 Correct 1552 ms 173712 KB Output is correct
16 Correct 1512 ms 173784 KB Output is correct
17 Correct 1441 ms 173988 KB Output is correct
18 Correct 3222 ms 161432 KB Output is correct
19 Correct 3267 ms 161540 KB Output is correct
20 Correct 3058 ms 161660 KB Output is correct
21 Correct 2647 ms 160932 KB Output is correct
22 Correct 2585 ms 161120 KB Output is correct
23 Correct 2700 ms 161124 KB Output is correct
24 Correct 2871 ms 161112 KB Output is correct
25 Correct 832 ms 164540 KB Output is correct
26 Correct 890 ms 164612 KB Output is correct
27 Correct 569 ms 164456 KB Output is correct
28 Correct 386 ms 161340 KB Output is correct
29 Correct 404 ms 161272 KB Output is correct
30 Correct 2747 ms 161564 KB Output is correct
31 Correct 2706 ms 161532 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 16 ms 12500 KB Output is correct
3 Correct 13 ms 12500 KB Output is correct
4 Correct 14 ms 12452 KB Output is correct
5 Correct 817 ms 134128 KB Output is correct
6 Correct 661 ms 124304 KB Output is correct
7 Correct 1085 ms 126440 KB Output is correct
8 Correct 1413 ms 168580 KB Output is correct
9 Correct 1385 ms 169336 KB Output is correct
10 Correct 1407 ms 169976 KB Output is correct
11 Correct 470 ms 172392 KB Output is correct
12 Correct 637 ms 167584 KB Output is correct
13 Correct 458 ms 172744 KB Output is correct
14 Correct 423 ms 173536 KB Output is correct
15 Correct 357 ms 172036 KB Output is correct
16 Correct 1035 ms 168116 KB Output is correct
17 Correct 1038 ms 169732 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9900 KB Output is correct
5 Correct 13 ms 12076 KB Output is correct
6 Correct 14 ms 12228 KB Output is correct
7 Correct 12 ms 11556 KB Output is correct
8 Correct 16 ms 12328 KB Output is correct
9 Correct 17 ms 12244 KB Output is correct
10 Correct 15 ms 12244 KB Output is correct
11 Correct 14 ms 12332 KB Output is correct
12 Correct 14 ms 12244 KB Output is correct
13 Correct 15 ms 12452 KB Output is correct
14 Correct 15 ms 12448 KB Output is correct
15 Correct 13 ms 12360 KB Output is correct
16 Correct 16 ms 12392 KB Output is correct
17 Correct 14 ms 12328 KB Output is correct
18 Correct 16 ms 12324 KB Output is correct
19 Correct 15 ms 12244 KB Output is correct
20 Correct 13 ms 12328 KB Output is correct
21 Correct 14 ms 12320 KB Output is correct
22 Correct 14 ms 12244 KB Output is correct
23 Correct 12 ms 12320 KB Output is correct
24 Correct 11 ms 12320 KB Output is correct
25 Correct 11 ms 12372 KB Output is correct
26 Correct 10 ms 12244 KB Output is correct
27 Correct 9 ms 12328 KB Output is correct
28 Correct 12 ms 12272 KB Output is correct
29 Correct 13 ms 12332 KB Output is correct
30 Correct 17 ms 12324 KB Output is correct
31 Correct 15 ms 12336 KB Output is correct
32 Correct 14 ms 12244 KB Output is correct
33 Correct 12 ms 12408 KB Output is correct
34 Correct 13 ms 12456 KB Output is correct
35 Correct 11 ms 12452 KB Output is correct
36 Correct 5 ms 9940 KB Output is correct
37 Correct 17 ms 12228 KB Output is correct
38 Correct 15 ms 12316 KB Output is correct
39 Correct 17 ms 12244 KB Output is correct
40 Correct 2424 ms 150540 KB Output is correct
41 Correct 2029 ms 123168 KB Output is correct
42 Correct 1724 ms 121380 KB Output is correct
43 Correct 1529 ms 119968 KB Output is correct
44 Correct 1646 ms 123348 KB Output is correct
45 Correct 2769 ms 161492 KB Output is correct
46 Correct 2726 ms 161520 KB Output is correct
47 Correct 2771 ms 161524 KB Output is correct
48 Correct 2926 ms 161628 KB Output is correct
49 Correct 3103 ms 161504 KB Output is correct
50 Correct 1552 ms 173712 KB Output is correct
51 Correct 1512 ms 173784 KB Output is correct
52 Correct 1441 ms 173988 KB Output is correct
53 Correct 3222 ms 161432 KB Output is correct
54 Correct 3267 ms 161540 KB Output is correct
55 Correct 3058 ms 161660 KB Output is correct
56 Correct 2647 ms 160932 KB Output is correct
57 Correct 2585 ms 161120 KB Output is correct
58 Correct 2700 ms 161124 KB Output is correct
59 Correct 2871 ms 161112 KB Output is correct
60 Correct 832 ms 164540 KB Output is correct
61 Correct 890 ms 164612 KB Output is correct
62 Correct 569 ms 164456 KB Output is correct
63 Correct 386 ms 161340 KB Output is correct
64 Correct 404 ms 161272 KB Output is correct
65 Correct 2747 ms 161564 KB Output is correct
66 Correct 2706 ms 161532 KB Output is correct
67 Correct 6 ms 9812 KB Output is correct
68 Correct 16 ms 12500 KB Output is correct
69 Correct 13 ms 12500 KB Output is correct
70 Correct 14 ms 12452 KB Output is correct
71 Correct 817 ms 134128 KB Output is correct
72 Correct 661 ms 124304 KB Output is correct
73 Correct 1085 ms 126440 KB Output is correct
74 Correct 1413 ms 168580 KB Output is correct
75 Correct 1385 ms 169336 KB Output is correct
76 Correct 1407 ms 169976 KB Output is correct
77 Correct 470 ms 172392 KB Output is correct
78 Correct 637 ms 167584 KB Output is correct
79 Correct 458 ms 172744 KB Output is correct
80 Correct 423 ms 173536 KB Output is correct
81 Correct 357 ms 172036 KB Output is correct
82 Correct 1035 ms 168116 KB Output is correct
83 Correct 1038 ms 169732 KB Output is correct
84 Correct 2371 ms 141244 KB Output is correct
85 Correct 1917 ms 113900 KB Output is correct
86 Correct 1297 ms 93852 KB Output is correct
87 Correct 2970 ms 161452 KB Output is correct
88 Correct 3102 ms 160828 KB Output is correct
89 Correct 2990 ms 161464 KB Output is correct
90 Correct 2973 ms 161464 KB Output is correct
91 Correct 3000 ms 161456 KB Output is correct
92 Correct 1530 ms 168976 KB Output is correct
93 Correct 1460 ms 168184 KB Output is correct
94 Correct 3066 ms 161608 KB Output is correct
95 Correct 3002 ms 161712 KB Output is correct
96 Correct 3083 ms 161480 KB Output is correct
97 Correct 3070 ms 161564 KB Output is correct
98 Correct 2483 ms 161108 KB Output is correct
99 Correct 2391 ms 160992 KB Output is correct
100 Correct 2451 ms 160828 KB Output is correct
101 Correct 2446 ms 161092 KB Output is correct
102 Correct 474 ms 164448 KB Output is correct
103 Correct 687 ms 164556 KB Output is correct
104 Correct 775 ms 164532 KB Output is correct
105 Correct 351 ms 161628 KB Output is correct
106 Correct 341 ms 161016 KB Output is correct
107 Correct 2379 ms 161428 KB Output is correct
108 Correct 2491 ms 161384 KB Output is correct