oj.uz

답안 #727729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727729 2023-04-21T07:56:47 Z fatemetmhr Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 963 ms 395164 KB 
// Be name khoda //

#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

const int maxn5 = 1e6 + 10;
const int maxnt = 4e6 + 10;

ll lim, cnt[maxn5][2], sum[maxn5][2], c[maxn5], x[maxn5];
vector <int> av[maxnt][3];
int par[maxn5], edpt = 0, ed[maxn5], a[maxn5];
int l[maxn5], r[maxn5], b[maxn5], pt[maxn5];
vector <pair<int, pair<int, int>>> ch;
bool mark[maxn5];

inline bool cmp(int i, int j){return abs(c[i] - lim) < abs(c[j] - lim) || (abs(c[i] - lim) == abs(c[j] - lim) && i < j);}
inline int get_par(int a){
    while(par[a] >= 0)
        a = par[a];
    return a;
}

inline void undo(int k){
    while(ch.size() > k){
        int a = ch.back().fi;
        int b = par[a];
        par[b] = ch.back().se.se;
        par[a] = ch.back().se.fi;
        ch.pop_back();
    }
}

inline bool merge(int a, int b){
    a = get_par(a);
    b = get_par(b);
    if(a == b)
        return false;
    if(-par[a] > -par[b])
        swap(a, b);
    ch.pb({a, {par[a], par[b]}});
    if(par[a] == par[b])
        par[b]--;
    par[a] = b;
    return true;
}

inline void mst(int x){
    lim = x;
    sort(ed, ed + edpt, cmp);
    int keep = ch.size();
    for(int i = 0; i < edpt; i++)
        mark[ed[i]] = merge(a[ed[i]], b[ed[i]]);
    undo(keep);
}

void solve(int lq, int rq, int v){
    int mid = (lq + rq) >> 1;
    edpt = 0;
    for(int i = 0; i < 3; i++)
        for(auto id : av[v][i])
            ed[edpt++] = id;
    mst(x[mid]);
    if(rq - lq == 1){
        for(auto id : av[v][0]){
            if(mark[id])
                r[id] = lq;
            else
                r[id] = lq - 1;
        }
        for(auto id : av[v][1]){
            if(mark[id])
                l[id] = r[id] = lq;
            else{
                l[id] = rq;
                r[id] = lq;
            }
        }
        for(auto id : av[v][2]){
            if(mark[id])
                l[id] = lq;
            else
                l[id] = rq;
        }
        return;
    }
    int keep = ch.size();
    for(auto id : av[v][0]){
        if(mark[id]){
            merge(a[id], b[id]);
            av[v * 2 + 1][0].pb(id);
        }
        else
            av[v * 2][0].pb(id);
    }
    for(auto id : av[v][1]){
        if(mark[id]){
            av[v * 2][2].pb(id);
            av[v * 2 + 1][0].pb(id);
        }
        else{
            if(pt[id] < mid)
                av[v * 2][1].pb(id);
            else
                av[v * 2 + 1][1].pb(id);
        }
    }
    vector <int> tomerge;
    for(auto id : av[v][2]){
        if(mark[id]){
            av[v * 2][2].pb(id);
            tomerge.pb(id);
        }
        else
            av[v * 2 + 1][2].pb(id);
    }
    solve(lq, mid, v * 2);
    undo(keep);
    for(auto id : tomerge)
        merge(a[id], b[id]);
    solve(mid, rq, v * 2 + 1);
    undo(keep);
}

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

    memset(par, -1, sizeof par);

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        av[1][1].pb(i);
    }
    int q; cin >> q;
    for(int i = 0; i < q; i++)
        cin >> x[i];
    for(int i = 0; i < m; i++)
        pt[i] = upper_bound(x, x + q, c[i]) - x - 1;
    solve(0, q, 1);
    for(int i = 0; i < m; i++) if(l[i] <= r[i]){
        if(x[l[i]] <= c[i]){
            cnt[l[i]][0]++;
            sum[l[i]][0] += c[i];
        }
        else{
            cnt[l[i]][1]++;
            sum[l[i]][1] -= c[i];
        }
        if(x[r[i]] <= c[i]){
            cnt[r[i] + 1][0]--;
            sum[r[i] + 1][0] -= c[i];
        }
        else{
            cnt[r[i] + 1][1]--;
            sum[r[i] + 1][1] += c[i];
        }
        if(x[l[i]] <= c[i] && x[r[i]] > c[i]){
            cnt[pt[i] + 1][0]--;
            sum[pt[i] + 1][0] -= c[i];
            cnt[pt[i] + 1][1]++;
            sum[pt[i] + 1][1] -= c[i];
        }
    }
    ll cur[2] = {0, 0}, t[2] = {0, 0};
    for(int i = 0; i < q; i++){
        cur[0] += sum[i][0];
        cur[1] += sum[i][1];
        t[0] += cnt[i][0];
        t[1] += cnt[i][1];
        cout << cur[0] + cur[1] + t[0] * (-x[i]) + t[1] * x[i] << '\n';
    }
}

Compilation message

reconstruction.cpp: In function 'void undo(int)':
reconstruction.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while(ch.size() > k){
      |           ~~~~~~~~~~^~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 286072 KB Output is correct
2 Correct 133 ms 286032 KB Output is correct
3 Correct 136 ms 286004 KB Output is correct
4 Correct 141 ms 286028 KB Output is correct
5 Correct 132 ms 286012 KB Output is correct
6 Correct 132 ms 286096 KB Output is correct
7 Correct 130 ms 286104 KB Output is correct
8 Correct 133 ms 286072 KB Output is correct
9 Correct 133 ms 286044 KB Output is correct
10 Correct 129 ms 286064 KB Output is correct
11 Correct 139 ms 286112 KB Output is correct
12 Correct 141 ms 285984 KB Output is correct
13 Correct 130 ms 286108 KB Output is correct
14 Correct 130 ms 286068 KB Output is correct
15 Correct 143 ms 286108 KB Output is correct
16 Correct 133 ms 286032 KB Output is correct
17 Correct 132 ms 286032 KB Output is correct
18 Correct 131 ms 286112 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 286072 KB Output is correct
2 Correct 133 ms 286032 KB Output is correct
3 Correct 136 ms 286004 KB Output is correct
4 Correct 141 ms 286028 KB Output is correct
5 Correct 132 ms 286012 KB Output is correct
6 Correct 132 ms 286096 KB Output is correct
7 Correct 130 ms 286104 KB Output is correct
8 Correct 133 ms 286072 KB Output is correct
9 Correct 133 ms 286044 KB Output is correct
10 Correct 129 ms 286064 KB Output is correct
11 Correct 139 ms 286112 KB Output is correct
12 Correct 141 ms 285984 KB Output is correct
13 Correct 130 ms 286108 KB Output is correct
14 Correct 130 ms 286068 KB Output is correct
15 Correct 143 ms 286108 KB Output is correct
16 Correct 133 ms 286032 KB Output is correct
17 Correct 132 ms 286032 KB Output is correct
18 Correct 131 ms 286112 KB Output is correct
19 Correct 132 ms 286060 KB Output is correct
20 Correct 236 ms 293172 KB Output is correct
21 Correct 232 ms 293052 KB Output is correct
22 Correct 223 ms 292912 KB Output is correct
23 Correct 228 ms 293140 KB Output is correct
24 Correct 231 ms 293152 KB Output is correct
25 Correct 219 ms 293236 KB Output is correct
26 Correct 229 ms 293232 KB Output is correct
27 Correct 221 ms 292956 KB Output is correct
28 Correct 231 ms 293188 KB Output is correct
29 Correct 209 ms 293092 KB Output is correct
30 Correct 225 ms 293192 KB Output is correct
31 Correct 247 ms 292944 KB Output is correct
32 Correct 223 ms 292864 KB Output is correct
33 Correct 234 ms 293328 KB Output is correct
34 Correct 222 ms 293188 KB Output is correct
35 Correct 232 ms 293452 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 286072 KB Output is correct
2 Correct 146 ms 286108 KB Output is correct
3 Correct 133 ms 286224 KB Output is correct
4 Correct 937 ms 392232 KB Output is correct
5 Correct 929 ms 392396 KB Output is correct
6 Correct 942 ms 392308 KB Output is correct
7 Correct 890 ms 393384 KB Output is correct
8 Correct 858 ms 392504 KB Output is correct
9 Correct 789 ms 395164 KB Output is correct
10 Correct 716 ms 329828 KB Output is correct
11 Correct 676 ms 330552 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 286072 KB Output is correct
2 Correct 133 ms 286032 KB Output is correct
3 Correct 136 ms 286004 KB Output is correct
4 Correct 141 ms 286028 KB Output is correct
5 Correct 132 ms 286012 KB Output is correct
6 Correct 132 ms 286096 KB Output is correct
7 Correct 130 ms 286104 KB Output is correct
8 Correct 133 ms 286072 KB Output is correct
9 Correct 133 ms 286044 KB Output is correct
10 Correct 129 ms 286064 KB Output is correct
11 Correct 139 ms 286112 KB Output is correct
12 Correct 141 ms 285984 KB Output is correct
13 Correct 130 ms 286108 KB Output is correct
14 Correct 130 ms 286068 KB Output is correct
15 Correct 143 ms 286108 KB Output is correct
16 Correct 133 ms 286032 KB Output is correct
17 Correct 132 ms 286032 KB Output is correct
18 Correct 131 ms 286112 KB Output is correct
19 Correct 133 ms 286044 KB Output is correct
20 Correct 362 ms 326228 KB Output is correct
21 Correct 353 ms 326636 KB Output is correct
22 Correct 352 ms 326496 KB Output is correct
23 Correct 342 ms 326436 KB Output is correct
24 Correct 356 ms 326364 KB Output is correct
25 Correct 342 ms 326164 KB Output is correct
26 Correct 355 ms 323552 KB Output is correct
27 Correct 337 ms 316236 KB Output is correct
28 Correct 349 ms 326428 KB Output is correct
29 Correct 342 ms 326072 KB Output is correct
30 Correct 354 ms 321668 KB Output is correct
31 Correct 352 ms 321652 KB Output is correct
32 Correct 364 ms 316652 KB Output is correct
33 Correct 342 ms 315952 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 286072 KB Output is correct
2 Correct 133 ms 286032 KB Output is correct
3 Correct 136 ms 286004 KB Output is correct
4 Correct 141 ms 286028 KB Output is correct
5 Correct 132 ms 286012 KB Output is correct
6 Correct 132 ms 286096 KB Output is correct
7 Correct 130 ms 286104 KB Output is correct
8 Correct 133 ms 286072 KB Output is correct
9 Correct 133 ms 286044 KB Output is correct
10 Correct 129 ms 286064 KB Output is correct
11 Correct 139 ms 286112 KB Output is correct
12 Correct 141 ms 285984 KB Output is correct
13 Correct 130 ms 286108 KB Output is correct
14 Correct 130 ms 286068 KB Output is correct
15 Correct 143 ms 286108 KB Output is correct
16 Correct 133 ms 286032 KB Output is correct
17 Correct 132 ms 286032 KB Output is correct
18 Correct 131 ms 286112 KB Output is correct
19 Correct 132 ms 286060 KB Output is correct
20 Correct 236 ms 293172 KB Output is correct
21 Correct 232 ms 293052 KB Output is correct
22 Correct 223 ms 292912 KB Output is correct
23 Correct 228 ms 293140 KB Output is correct
24 Correct 231 ms 293152 KB Output is correct
25 Correct 219 ms 293236 KB Output is correct
26 Correct 229 ms 293232 KB Output is correct
27 Correct 221 ms 292956 KB Output is correct
28 Correct 231 ms 293188 KB Output is correct
29 Correct 209 ms 293092 KB Output is correct
30 Correct 225 ms 293192 KB Output is correct
31 Correct 247 ms 292944 KB Output is correct
32 Correct 223 ms 292864 KB Output is correct
33 Correct 234 ms 293328 KB Output is correct
34 Correct 222 ms 293188 KB Output is correct
35 Correct 232 ms 293452 KB Output is correct
36 Correct 484 ms 305636 KB Output is correct
37 Correct 486 ms 306172 KB Output is correct
38 Correct 485 ms 305996 KB Output is correct
39 Correct 500 ms 305996 KB Output is correct
40 Correct 512 ms 305940 KB Output is correct
41 Correct 491 ms 305796 KB Output is correct
42 Correct 486 ms 305736 KB Output is correct
43 Correct 487 ms 305748 KB Output is correct
44 Correct 503 ms 304568 KB Output is correct
45 Correct 306 ms 298676 KB Output is correct
46 Correct 486 ms 305628 KB Output is correct
47 Correct 522 ms 305676 KB Output is correct
48 Correct 457 ms 302684 KB Output is correct
49 Correct 457 ms 303244 KB Output is correct
50 Correct 318 ms 298156 KB Output is correct
51 Correct 422 ms 298460 KB Output is correct

Subtask #6
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 286072 KB Output is correct
2 Correct 133 ms 286032 KB Output is correct
3 Correct 136 ms 286004 KB Output is correct
4 Correct 141 ms 286028 KB Output is correct
5 Correct 132 ms 286012 KB Output is correct
6 Correct 132 ms 286096 KB Output is correct
7 Correct 130 ms 286104 KB Output is correct
8 Correct 133 ms 286072 KB Output is correct
9 Correct 133 ms 286044 KB Output is correct
10 Correct 129 ms 286064 KB Output is correct
11 Correct 139 ms 286112 KB Output is correct
12 Correct 141 ms 285984 KB Output is correct
13 Correct 130 ms 286108 KB Output is correct
14 Correct 130 ms 286068 KB Output is correct
15 Correct 143 ms 286108 KB Output is correct
16 Correct 133 ms 286032 KB Output is correct
17 Correct 132 ms 286032 KB Output is correct
18 Correct 131 ms 286112 KB Output is correct
19 Correct 132 ms 286060 KB Output is correct
20 Correct 236 ms 293172 KB Output is correct
21 Correct 232 ms 293052 KB Output is correct
22 Correct 223 ms 292912 KB Output is correct
23 Correct 228 ms 293140 KB Output is correct
24 Correct 231 ms 293152 KB Output is correct
25 Correct 219 ms 293236 KB Output is correct
26 Correct 229 ms 293232 KB Output is correct
27 Correct 221 ms 292956 KB Output is correct
28 Correct 231 ms 293188 KB Output is correct
29 Correct 209 ms 293092 KB Output is correct
30 Correct 225 ms 293192 KB Output is correct
31 Correct 247 ms 292944 KB Output is correct
32 Correct 223 ms 292864 KB Output is correct
33 Correct 234 ms 293328 KB Output is correct
34 Correct 222 ms 293188 KB Output is correct
35 Correct 232 ms 293452 KB Output is correct
36 Correct 132 ms 286072 KB Output is correct
37 Correct 146 ms 286108 KB Output is correct
38 Correct 133 ms 286224 KB Output is correct
39 Correct 937 ms 392232 KB Output is correct
40 Correct 929 ms 392396 KB Output is correct
41 Correct 942 ms 392308 KB Output is correct
42 Correct 890 ms 393384 KB Output is correct
43 Correct 858 ms 392504 KB Output is correct
44 Correct 789 ms 395164 KB Output is correct
45 Correct 716 ms 329828 KB Output is correct
46 Correct 676 ms 330552 KB Output is correct
47 Correct 133 ms 286044 KB Output is correct
48 Correct 362 ms 326228 KB Output is correct
49 Correct 353 ms 326636 KB Output is correct
50 Correct 352 ms 326496 KB Output is correct
51 Correct 342 ms 326436 KB Output is correct
52 Correct 356 ms 326364 KB Output is correct
53 Correct 342 ms 326164 KB Output is correct
54 Correct 355 ms 323552 KB Output is correct
55 Correct 337 ms 316236 KB Output is correct
56 Correct 349 ms 326428 KB Output is correct
57 Correct 342 ms 326072 KB Output is correct
58 Correct 354 ms 321668 KB Output is correct
59 Correct 352 ms 321652 KB Output is correct
60 Correct 364 ms 316652 KB Output is correct
61 Correct 342 ms 315952 KB Output is correct
62 Correct 484 ms 305636 KB Output is correct
63 Correct 486 ms 306172 KB Output is correct
64 Correct 485 ms 305996 KB Output is correct
65 Correct 500 ms 305996 KB Output is correct
66 Correct 512 ms 305940 KB Output is correct
67 Correct 491 ms 305796 KB Output is correct
68 Correct 486 ms 305736 KB Output is correct
69 Correct 487 ms 305748 KB Output is correct
70 Correct 503 ms 304568 KB Output is correct
71 Correct 306 ms 298676 KB Output is correct
72 Correct 486 ms 305628 KB Output is correct
73 Correct 522 ms 305676 KB Output is correct
74 Correct 457 ms 302684 KB Output is correct
75 Correct 457 ms 303244 KB Output is correct
76 Correct 318 ms 298156 KB Output is correct
77 Correct 422 ms 298460 KB Output is correct
78 Correct 933 ms 391312 KB Output is correct
79 Correct 925 ms 393492 KB Output is correct
80 Correct 914 ms 392596 KB Output is correct
81 Correct 920 ms 392572 KB Output is correct
82 Correct 924 ms 391484 KB Output is correct
83 Correct 935 ms 391292 KB Output is correct
84 Correct 963 ms 391268 KB Output is correct
85 Correct 943 ms 390732 KB Output is correct
86 Correct 820 ms 353084 KB Output is correct
87 Correct 555 ms 329960 KB Output is correct
88 Correct 931 ms 387876 KB Output is correct
89 Correct 930 ms 388012 KB Output is correct
90 Correct 832 ms 375820 KB Output is correct
91 Correct 835 ms 376184 KB Output is correct
92 Correct 554 ms 330028 KB Output is correct
93 Correct 676 ms 330204 KB Output is correct