oj.uz

Submission #897753

# Submission time Handle Problem Language Result Execution time Memory
897753 2024-01-03T16:00:51 Z cadmiumsky Security Guard (JOI23_guard) C++17
100 / 100
 1422 ms 290740 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

vector<int> S;

vector<int> g[nmax];

int occ[nmax];

tii subtr(tii a, int b) {
  auto [u, v, w] = a;
  return tii{u - b, v, w};
}

namespace DSU {
  int dsu[nmax], mn[nmax];
  
  int newnodecnt = 0;
  
  ll sum;
  
  ll mnsum = 0;
  
  vector<int> R;
  
  multiset<tii> overall;
  
  multiset<tii> edgs[nmax];
  
  void init(int n) {
    sum = 0;
    newnodecnt = n;
    for(int i = 0; i < n; i++) {
      mnsum += S[0] + S[i],
      dsu[i] = i, mn[i] = S[i];
      for(auto x : g[i])
          edgs[i].emplace(S[x] + S[i], i, x);
      overall.emplace(subtr(*edgs[i].begin(), S[i]));
    }
    
    mnsum -= S[0] * 2;
    
    R.emplace_back(sum + mnsum);
  }
  
  int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
  
  void unite(int x, int y, int Cost) {
    pii F = pii{x, y};
    x = f(x);
    y = f(y);
    if(x == y) assert(false);
    
    sum += S[F.first] + S[F.second];
    mnsum -= S[0] + max(mn[x], mn[y]);
    R.emplace_back(sum + mnsum);
    
    if(sz(edgs[x]) < sz(edgs[y])) swap(x, y);
    
    if(sz(edgs[x])) overall.erase(subtr(*edgs[x].begin(), mn[x]));
    if(sz(edgs[y])) overall.erase(subtr(*edgs[y].begin(), mn[y]));
    
    dsu[y] = x;
    mn[x] = min(mn[x], mn[y]);
    for(auto [C, a, b] : edgs[y])
      edgs[x].emplace(C, a, b);
    
    while(sz(edgs[x]) > 0 && f(get<1>(*edgs[x].begin())) == f(get<2>(*edgs[x].begin()))) edgs[x].erase(edgs[x].begin());
    
    if(sz(edgs[x]))
      overall.emplace(subtr(*edgs[x].begin(), mn[x]));
  }
  
  void generate() {
    while(!overall.empty()) { 
      auto [a, b, c] = *overall.begin();
      unite(b, c, a);
    }
    return;
  }
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m, q;
  cin >> n >> m >> q;
  
  S.resize(n);
  
  for(auto &x : S) cin >> x;
  
  vector<int> dir_ord(n), reidx(n + 1);
  
  iota(all(dir_ord), 0);
  sort(all(dir_ord), [&](int a, int b) { return S[a] < S[b]; });
  sort(all(S));
  
  for(int i = 0; i < n; i++)
    reidx[dir_ord[i] + 1] = i;

  //for(auto x : reidx) cerr << x << ' '; cerr << '\n';

  vector<tii> edg;
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    
    a = reidx[a];
    b = reidx[b];
    
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  
  DSU::init(n);
  DSU::generate();
  
  vector<int> R = move(DSU::R);
  
  reverse(all(R));
  R.resize(q + 1, R.back());
  
  ll delta =  - accumulate(all(S), 0LL) + (*max_element(all(S)));
  for(auto x : R)
    cout << x + delta << '\n';
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 209 ms 69796 KB Output is correct
3 Correct 211 ms 69832 KB Output is correct
4 Correct 267 ms 69832 KB Output is correct
5 Correct 256 ms 69832 KB Output is correct
6 Correct 260 ms 69724 KB Output is correct
7 Correct 298 ms 69868 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 209 ms 69796 KB Output is correct
3 Correct 211 ms 69832 KB Output is correct
4 Correct 267 ms 69832 KB Output is correct
5 Correct 256 ms 69832 KB Output is correct
6 Correct 260 ms 69724 KB Output is correct
7 Correct 298 ms 69868 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 659 ms 69828 KB Output is correct
11 Correct 217 ms 69872 KB Output is correct
12 Correct 210 ms 69828 KB Output is correct
13 Correct 214 ms 69812 KB Output is correct
14 Correct 690 ms 69800 KB Output is correct
15 Correct 642 ms 69712 KB Output is correct
16 Correct 662 ms 69944 KB Output is correct
17 Correct 642 ms 69784 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 209 ms 69796 KB Output is correct
3 Correct 211 ms 69832 KB Output is correct
4 Correct 267 ms 69832 KB Output is correct
5 Correct 256 ms 69832 KB Output is correct
6 Correct 260 ms 69724 KB Output is correct
7 Correct 298 ms 69868 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 659 ms 69828 KB Output is correct
11 Correct 217 ms 69872 KB Output is correct
12 Correct 210 ms 69828 KB Output is correct
13 Correct 214 ms 69812 KB Output is correct
14 Correct 690 ms 69800 KB Output is correct
15 Correct 642 ms 69712 KB Output is correct
16 Correct 662 ms 69944 KB Output is correct
17 Correct 642 ms 69784 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 687 ms 70908 KB Output is correct
20 Correct 657 ms 70864 KB Output is correct
21 Correct 687 ms 70856 KB Output is correct
22 Correct 652 ms 71108 KB Output is correct
23 Correct 530 ms 71632 KB Output is correct
24 Correct 473 ms 72416 KB Output is correct
25 Correct 383 ms 77108 KB Output is correct
26 Correct 328 ms 71868 KB Output is correct
27 Correct 346 ms 72388 KB Output is correct
28 Correct 607 ms 70116 KB Output is correct
29 Correct 507 ms 70596 KB Output is correct
30 Correct 350 ms 71160 KB Output is correct
31 Correct 358 ms 72196 KB Output is correct
32 Correct 636 ms 71492 KB Output is correct
33 Correct 395 ms 72072 KB Output is correct
34 Correct 537 ms 146884 KB Output is correct
35 Correct 582 ms 151244 KB Output is correct
36 Correct 480 ms 128364 KB Output is correct
37 Correct 434 ms 122072 KB Output is correct
38 Correct 337 ms 71804 KB Output is correct
39 Correct 278 ms 70720 KB Output is correct
40 Correct 305 ms 71416 KB Output is correct
41 Correct 298 ms 69708 KB Output is correct
42 Correct 261 ms 69756 KB Output is correct
43 Correct 579 ms 71088 KB Output is correct
44 Correct 661 ms 71136 KB Output is correct
45 Correct 538 ms 71304 KB Output is correct
46 Correct 506 ms 71108 KB Output is correct
47 Correct 567 ms 71072 KB Output is correct
48 Correct 628 ms 71168 KB Output is correct
49 Correct 298 ms 71204 KB Output is correct
50 Correct 389 ms 71112 KB Output is correct
51 Correct 546 ms 71164 KB Output is correct
52 Correct 570 ms 71152 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 209 ms 69796 KB Output is correct
3 Correct 211 ms 69832 KB Output is correct
4 Correct 267 ms 69832 KB Output is correct
5 Correct 256 ms 69832 KB Output is correct
6 Correct 260 ms 69724 KB Output is correct
7 Correct 298 ms 69868 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 659 ms 69828 KB Output is correct
11 Correct 217 ms 69872 KB Output is correct
12 Correct 210 ms 69828 KB Output is correct
13 Correct 214 ms 69812 KB Output is correct
14 Correct 690 ms 69800 KB Output is correct
15 Correct 642 ms 69712 KB Output is correct
16 Correct 662 ms 69944 KB Output is correct
17 Correct 642 ms 69784 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 687 ms 70908 KB Output is correct
20 Correct 657 ms 70864 KB Output is correct
21 Correct 687 ms 70856 KB Output is correct
22 Correct 652 ms 71108 KB Output is correct
23 Correct 530 ms 71632 KB Output is correct
24 Correct 473 ms 72416 KB Output is correct
25 Correct 383 ms 77108 KB Output is correct
26 Correct 328 ms 71868 KB Output is correct
27 Correct 346 ms 72388 KB Output is correct
28 Correct 607 ms 70116 KB Output is correct
29 Correct 507 ms 70596 KB Output is correct
30 Correct 350 ms 71160 KB Output is correct
31 Correct 358 ms 72196 KB Output is correct
32 Correct 636 ms 71492 KB Output is correct
33 Correct 395 ms 72072 KB Output is correct
34 Correct 537 ms 146884 KB Output is correct
35 Correct 582 ms 151244 KB Output is correct
36 Correct 480 ms 128364 KB Output is correct
37 Correct 434 ms 122072 KB Output is correct
38 Correct 337 ms 71804 KB Output is correct
39 Correct 278 ms 70720 KB Output is correct
40 Correct 305 ms 71416 KB Output is correct
41 Correct 298 ms 69708 KB Output is correct
42 Correct 261 ms 69756 KB Output is correct
43 Correct 579 ms 71088 KB Output is correct
44 Correct 661 ms 71136 KB Output is correct
45 Correct 538 ms 71304 KB Output is correct
46 Correct 506 ms 71108 KB Output is correct
47 Correct 567 ms 71072 KB Output is correct
48 Correct 628 ms 71168 KB Output is correct
49 Correct 298 ms 71204 KB Output is correct
50 Correct 389 ms 71112 KB Output is correct
51 Correct 546 ms 71164 KB Output is correct
52 Correct 570 ms 71152 KB Output is correct
53 Correct 3 ms 19036 KB Output is correct
54 Correct 700 ms 72484 KB Output is correct
55 Correct 684 ms 72756 KB Output is correct
56 Correct 929 ms 91108 KB Output is correct
57 Correct 1292 ms 152508 KB Output is correct
58 Correct 970 ms 178700 KB Output is correct
59 Correct 877 ms 134596 KB Output is correct
60 Correct 503 ms 90040 KB Output is correct
61 Correct 802 ms 134692 KB Output is correct
62 Correct 738 ms 101048 KB Output is correct
63 Correct 623 ms 72360 KB Output is correct
64 Correct 718 ms 83904 KB Output is correct
65 Correct 734 ms 101948 KB Output is correct
66 Correct 700 ms 101240 KB Output is correct
67 Correct 1079 ms 116316 KB Output is correct
68 Correct 369 ms 72096 KB Output is correct
69 Correct 997 ms 283548 KB Output is correct
70 Correct 635 ms 173936 KB Output is correct
71 Correct 435 ms 128204 KB Output is correct
72 Correct 432 ms 121844 KB Output is correct
73 Correct 328 ms 71636 KB Output is correct
74 Correct 276 ms 70656 KB Output is correct
75 Correct 297 ms 71108 KB Output is correct
76 Correct 291 ms 70060 KB Output is correct
77 Correct 262 ms 69828 KB Output is correct
78 Correct 586 ms 73156 KB Output is correct
79 Correct 1292 ms 148684 KB Output is correct
80 Correct 707 ms 92920 KB Output is correct
81 Correct 914 ms 139744 KB Output is correct
82 Correct 1095 ms 154092 KB Output is correct
83 Correct 1316 ms 149708 KB Output is correct
84 Correct 675 ms 100856 KB Output is correct
85 Correct 390 ms 71172 KB Output is correct
86 Correct 544 ms 71120 KB Output is correct
87 Correct 541 ms 71072 KB Output is correct
88 Correct 1422 ms 181700 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 4 ms 19240 KB Output is correct
7 Correct 5 ms 19288 KB Output is correct
8 Correct 17 ms 22800 KB Output is correct
9 Correct 17 ms 22872 KB Output is correct
10 Correct 15 ms 22620 KB Output is correct
11 Correct 16 ms 22872 KB Output is correct
12 Correct 16 ms 22876 KB Output is correct
13 Correct 16 ms 22876 KB Output is correct
14 Correct 20 ms 22836 KB Output is correct
15 Correct 16 ms 22876 KB Output is correct
16 Correct 16 ms 22988 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 4 ms 19240 KB Output is correct
7 Correct 5 ms 19288 KB Output is correct
8 Correct 17 ms 22800 KB Output is correct
9 Correct 17 ms 22872 KB Output is correct
10 Correct 15 ms 22620 KB Output is correct
11 Correct 16 ms 22872 KB Output is correct
12 Correct 16 ms 22876 KB Output is correct
13 Correct 16 ms 22876 KB Output is correct
14 Correct 20 ms 22836 KB Output is correct
15 Correct 16 ms 22876 KB Output is correct
16 Correct 16 ms 22988 KB Output is correct
17 Correct 54 ms 31340 KB Output is correct
18 Correct 48 ms 32848 KB Output is correct
19 Correct 127 ms 55632 KB Output is correct
20 Correct 293 ms 93144 KB Output is correct
21 Correct 346 ms 116576 KB Output is correct
22 Correct 269 ms 67512 KB Output is correct
23 Correct 638 ms 106836 KB Output is correct
24 Correct 370 ms 88704 KB Output is correct
25 Correct 19 ms 23900 KB Output is correct
26 Correct 317 ms 112424 KB Output is correct
27 Correct 68 ms 38836 KB Output is correct
28 Correct 19 ms 23644 KB Output is correct
29 Correct 23 ms 23900 KB Output is correct
30 Correct 19 ms 23820 KB Output is correct
31 Correct 17 ms 22620 KB Output is correct
32 Correct 17 ms 22620 KB Output is correct
33 Correct 24 ms 25172 KB Output is correct
34 Correct 30 ms 27220 KB Output is correct
35 Correct 163 ms 62052 KB Output is correct
36 Correct 776 ms 163488 KB Output is correct

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 209 ms 69796 KB Output is correct
3 Correct 211 ms 69832 KB Output is correct
4 Correct 267 ms 69832 KB Output is correct
5 Correct 256 ms 69832 KB Output is correct
6 Correct 260 ms 69724 KB Output is correct
7 Correct 298 ms 69868 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 659 ms 69828 KB Output is correct
11 Correct 217 ms 69872 KB Output is correct
12 Correct 210 ms 69828 KB Output is correct
13 Correct 214 ms 69812 KB Output is correct
14 Correct 690 ms 69800 KB Output is correct
15 Correct 642 ms 69712 KB Output is correct
16 Correct 662 ms 69944 KB Output is correct
17 Correct 642 ms 69784 KB Output is correct
18 Correct 4 ms 19036 KB Output is correct
19 Correct 687 ms 70908 KB Output is correct
20 Correct 657 ms 70864 KB Output is correct
21 Correct 687 ms 70856 KB Output is correct
22 Correct 652 ms 71108 KB Output is correct
23 Correct 530 ms 71632 KB Output is correct
24 Correct 473 ms 72416 KB Output is correct
25 Correct 383 ms 77108 KB Output is correct
26 Correct 328 ms 71868 KB Output is correct
27 Correct 346 ms 72388 KB Output is correct
28 Correct 607 ms 70116 KB Output is correct
29 Correct 507 ms 70596 KB Output is correct
30 Correct 350 ms 71160 KB Output is correct
31 Correct 358 ms 72196 KB Output is correct
32 Correct 636 ms 71492 KB Output is correct
33 Correct 395 ms 72072 KB Output is correct
34 Correct 537 ms 146884 KB Output is correct
35 Correct 582 ms 151244 KB Output is correct
36 Correct 480 ms 128364 KB Output is correct
37 Correct 434 ms 122072 KB Output is correct
38 Correct 337 ms 71804 KB Output is correct
39 Correct 278 ms 70720 KB Output is correct
40 Correct 305 ms 71416 KB Output is correct
41 Correct 298 ms 69708 KB Output is correct
42 Correct 261 ms 69756 KB Output is correct
43 Correct 579 ms 71088 KB Output is correct
44 Correct 661 ms 71136 KB Output is correct
45 Correct 538 ms 71304 KB Output is correct
46 Correct 506 ms 71108 KB Output is correct
47 Correct 567 ms 71072 KB Output is correct
48 Correct 628 ms 71168 KB Output is correct
49 Correct 298 ms 71204 KB Output is correct
50 Correct 389 ms 71112 KB Output is correct
51 Correct 546 ms 71164 KB Output is correct
52 Correct 570 ms 71152 KB Output is correct
53 Correct 3 ms 19036 KB Output is correct
54 Correct 700 ms 72484 KB Output is correct
55 Correct 684 ms 72756 KB Output is correct
56 Correct 929 ms 91108 KB Output is correct
57 Correct 1292 ms 152508 KB Output is correct
58 Correct 970 ms 178700 KB Output is correct
59 Correct 877 ms 134596 KB Output is correct
60 Correct 503 ms 90040 KB Output is correct
61 Correct 802 ms 134692 KB Output is correct
62 Correct 738 ms 101048 KB Output is correct
63 Correct 623 ms 72360 KB Output is correct
64 Correct 718 ms 83904 KB Output is correct
65 Correct 734 ms 101948 KB Output is correct
66 Correct 700 ms 101240 KB Output is correct
67 Correct 1079 ms 116316 KB Output is correct
68 Correct 369 ms 72096 KB Output is correct
69 Correct 997 ms 283548 KB Output is correct
70 Correct 635 ms 173936 KB Output is correct
71 Correct 435 ms 128204 KB Output is correct
72 Correct 432 ms 121844 KB Output is correct
73 Correct 328 ms 71636 KB Output is correct
74 Correct 276 ms 70656 KB Output is correct
75 Correct 297 ms 71108 KB Output is correct
76 Correct 291 ms 70060 KB Output is correct
77 Correct 262 ms 69828 KB Output is correct
78 Correct 586 ms 73156 KB Output is correct
79 Correct 1292 ms 148684 KB Output is correct
80 Correct 707 ms 92920 KB Output is correct
81 Correct 914 ms 139744 KB Output is correct
82 Correct 1095 ms 154092 KB Output is correct
83 Correct 1316 ms 149708 KB Output is correct
84 Correct 675 ms 100856 KB Output is correct
85 Correct 390 ms 71172 KB Output is correct
86 Correct 544 ms 71120 KB Output is correct
87 Correct 541 ms 71072 KB Output is correct
88 Correct 1422 ms 181700 KB Output is correct
89 Correct 3 ms 19036 KB Output is correct
90 Correct 4 ms 19036 KB Output is correct
91 Correct 4 ms 19036 KB Output is correct
92 Correct 4 ms 19036 KB Output is correct
93 Correct 3 ms 19036 KB Output is correct
94 Correct 4 ms 19240 KB Output is correct
95 Correct 5 ms 19288 KB Output is correct
96 Correct 17 ms 22800 KB Output is correct
97 Correct 17 ms 22872 KB Output is correct
98 Correct 15 ms 22620 KB Output is correct
99 Correct 16 ms 22872 KB Output is correct
100 Correct 16 ms 22876 KB Output is correct
101 Correct 16 ms 22876 KB Output is correct
102 Correct 20 ms 22836 KB Output is correct
103 Correct 16 ms 22876 KB Output is correct
104 Correct 16 ms 22988 KB Output is correct
105 Correct 54 ms 31340 KB Output is correct
106 Correct 48 ms 32848 KB Output is correct
107 Correct 127 ms 55632 KB Output is correct
108 Correct 293 ms 93144 KB Output is correct
109 Correct 346 ms 116576 KB Output is correct
110 Correct 269 ms 67512 KB Output is correct
111 Correct 638 ms 106836 KB Output is correct
112 Correct 370 ms 88704 KB Output is correct
113 Correct 19 ms 23900 KB Output is correct
114 Correct 317 ms 112424 KB Output is correct
115 Correct 68 ms 38836 KB Output is correct
116 Correct 19 ms 23644 KB Output is correct
117 Correct 23 ms 23900 KB Output is correct
118 Correct 19 ms 23820 KB Output is correct
119 Correct 17 ms 22620 KB Output is correct
120 Correct 17 ms 22620 KB Output is correct
121 Correct 24 ms 25172 KB Output is correct
122 Correct 30 ms 27220 KB Output is correct
123 Correct 163 ms 62052 KB Output is correct
124 Correct 776 ms 163488 KB Output is correct
125 Correct 714 ms 79808 KB Output is correct
126 Correct 731 ms 80204 KB Output is correct
127 Correct 916 ms 100212 KB Output is correct
128 Correct 1399 ms 167876 KB Output is correct
129 Correct 846 ms 146972 KB Output is correct
130 Correct 891 ms 154824 KB Output is correct
131 Correct 845 ms 132432 KB Output is correct
132 Correct 705 ms 117804 KB Output is correct
133 Correct 705 ms 109632 KB Output is correct
134 Correct 622 ms 82628 KB Output is correct
135 Correct 650 ms 86716 KB Output is correct
136 Correct 774 ms 128132 KB Output is correct
137 Correct 687 ms 110492 KB Output is correct
138 Correct 1119 ms 134460 KB Output is correct
139 Correct 415 ms 77460 KB Output is correct
140 Correct 1008 ms 290740 KB Output is correct
141 Correct 643 ms 180868 KB Output is correct
142 Correct 453 ms 135364 KB Output is correct
143 Correct 442 ms 129348 KB Output is correct
144 Correct 360 ms 78260 KB Output is correct
145 Correct 300 ms 77120 KB Output is correct
146 Correct 328 ms 77412 KB Output is correct
147 Correct 316 ms 75460 KB Output is correct
148 Correct 314 ms 75456 KB Output is correct
149 Correct 641 ms 78704 KB Output is correct
150 Correct 1221 ms 167464 KB Output is correct
151 Correct 724 ms 94184 KB Output is correct
152 Correct 978 ms 154168 KB Output is correct
153 Correct 1126 ms 158856 KB Output is correct
154 Correct 1255 ms 158952 KB Output is correct
155 Correct 658 ms 110448 KB Output is correct
156 Correct 368 ms 78020 KB Output is correct
157 Correct 529 ms 78516 KB Output is correct
158 Correct 525 ms 74944 KB Output is correct
159 Correct 1341 ms 191552 KB Output is correct