oj.uz

답안 #922244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922244 2024-02-05T09:39:04 Z bohicob493 다리 (APIO19_bridges) C++17
100 / 100
 1556 ms 36092 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 5e4 + 1, SQ = 900;

int wei[MAXN * 2], par[MAXN], sz[MAXN];
PII edg[MAXN * 2];
bool marke[MAXN * 2];
struct Query {
    int t, x, y;
} quer[MAXN * 2];
VI bucket[MAXN * 4];
int ans[MAXN * 2];
VI N[MAXN];
bool mark[MAXN];
int lstw[MAXN * 2];

int gp(int v){
    return par[v] == v ? v : par[v] = gp(par[v]);
}

void merge(int u, int v){
    u = gp(u), v = gp(v);
    if (u == v) return;
    par[u] = v;
    sz[v] += sz[u];
}

int sigma, globpnt;
int trash[MAXN];
int dfsarr[MAXN];
void dfs(int v){
    /*
    trash[++globpnt] = v;
    mark[v] = 1;
    sigma += sz[v];
    for (int u : N[v]){
        if (!mark[u]) dfs(u);
    }
    */
    int curpnt = 1, szz = 1;
    dfsarr[1] = v;
    mark[v] = 1;
    while (curpnt <= szz){
        int u = dfsarr[curpnt];
        trash[++globpnt] = u;
        sigma += sz[u];
        for (int w : N[u]){
            if (!mark[w]){
                dfsarr[++szz] = w;
                mark[w] = 1;
            }
        }
        curpnt++;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    VI cmpr;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v >> wei[i];
        edg[i] = MP(u, v);
        cmpr.PB(wei[i]);
    }
    int q; cin >> q;
    for (int i = 0; i < q; i++){
        cin >> quer[i].t >> quer[i].x >> quer[i].y;
        cmpr.PB(quer[i].y);
    }
    sort(all(cmpr));
    cmpr.resize(unique(all(cmpr)) - cmpr.begin());
    for (int i = 1; i <= m; i++){
        wei[i] = lower_bound(all(cmpr), wei[i]) - cmpr.begin() + 1;
        lstw[i] = wei[i];
    }
    for (int i = 0; i < q; i++){
        quer[i].y = lower_bound(all(cmpr), quer[i].y) - cmpr.begin() + 1;
    }
    int mxwei = cmpr.size();
    for (int i = 0; i < q; i++){
        if (i % SQ) continue;
        //cout << "#1" << endl;
        vector<PII> procs;
        VI upds;
        for (int j = i; j < min(i + SQ, q); j++){
            if (quer[j].t == 1){
                marke[quer[j].x] = 1;
                upds.PB(j);
            } else {
                procs.PB(MP(-quer[j].y, j));
            }
        }
        //for (int j = 1; j <= m; j++) cout << marke[j];
        //cout << endl;
        for (int j = 1; j <= m; j++){
            if (marke[j]) continue;
            bucket[wei[j]].PB(j);
            //cout << "added " << j << ' ' << wei[j] << ' ' << " to bucket" << endl;
        }
        fill(sz, sz + n + 1, 1);
        iota(par, par + n + 1, 0);
        sort(all(procs));
        int pnt = mxwei;
        for (auto [tmpw, id] : procs){
            int W = -tmpw;
            //cout << "proces : ";
            //cout << id+1 << ' ' << W << endl;
            while (pnt >= W){
                for (int E : bucket[pnt]){
                    merge(edg[E].first, edg[E].second);
                    //cout << "merged " << edg[E].first << ' ' << edg[E].second << endl;
                }
                pnt--;
            }
            for (int j : upds){
                if (j > id) break;
                lstw[quer[j].x] = quer[j].y;
            }
            for (int j : upds){
                if (lstw[quer[j].x] && lstw[quer[j].x] >= W){
                    auto [u, v] = edg[quer[j].x];
                    u = gp(u);
                    v = gp(v);
                    N[u].PB(v);
                    N[v].PB(u);
                    //cout << "add edg " << u << ' ' << v << endl;
                }
            }
            sigma = 0;
            globpnt = 0;
            dfs(gp(quer[id].x));
            ans[id] = sigma;
            for (int j = 1; j <= globpnt; j++) mark[trash[j]] = 0;
            ////////////////////////////////////////////
            for (int j : upds){
                if (lstw[quer[j].x] && lstw[quer[j].x] >= W){
                    auto [u, v] = edg[quer[j].x];
                    u = gp(u);
                    v = gp(v);
                    N[u].pop_back();
                    N[v].pop_back();
                    //cout << "rmv edg " << u << ' ' << v << endl;
                }
            }
            for (int j : upds){
                if (j > id) break;
                lstw[quer[j].x] = wei[quer[j].x];
            }
        }
        for (int j = 1; j <= m; j++){
            if (marke[j]) continue;
            bucket[wei[j]].clear();
        }
        for (int j = i; j < min(i + SQ, q); j++){
            if (quer[j].t == 1){
                marke[quer[j].x] = 0;
                lstw[quer[j].x] = wei[quer[j].x] = quer[j].y;
            }
        }
    }
    for (int i = 0; i < q; i++){
        if (ans[i]) cout << ans[i] << endl;
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 34 ms 8796 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 36 ms 8788 KB Output is correct
6 Correct 29 ms 8792 KB Output is correct
7 Correct 30 ms 8796 KB Output is correct
8 Correct 34 ms 8536 KB Output is correct
9 Correct 38 ms 8764 KB Output is correct
10 Correct 33 ms 8784 KB Output is correct
11 Correct 35 ms 8540 KB Output is correct
12 Correct 38 ms 8540 KB Output is correct
13 Correct 36 ms 8788 KB Output is correct
14 Correct 36 ms 8788 KB Output is correct
15 Correct 46 ms 8768 KB Output is correct
16 Correct 38 ms 8780 KB Output is correct
17 Correct 34 ms 8780 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 14644 KB Output is correct
2 Correct 682 ms 14540 KB Output is correct
3 Correct 691 ms 14924 KB Output is correct
4 Correct 698 ms 14628 KB Output is correct
5 Correct 685 ms 14800 KB Output is correct
6 Correct 972 ms 14756 KB Output is correct
7 Correct 927 ms 14480 KB Output is correct
8 Correct 871 ms 14612 KB Output is correct
9 Correct 73 ms 9204 KB Output is correct
10 Correct 641 ms 11608 KB Output is correct
11 Correct 552 ms 11984 KB Output is correct
12 Correct 426 ms 12744 KB Output is correct
13 Correct 583 ms 15868 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 707 ms 18236 KB Output is correct
2 Correct 617 ms 15080 KB Output is correct
3 Correct 891 ms 22684 KB Output is correct
4 Correct 809 ms 28092 KB Output is correct
5 Correct 71 ms 9184 KB Output is correct
6 Correct 930 ms 25352 KB Output is correct
7 Correct 752 ms 24840 KB Output is correct
8 Correct 668 ms 20684 KB Output is correct
9 Correct 525 ms 14792 KB Output is correct
10 Correct 469 ms 13912 KB Output is correct
11 Correct 599 ms 24808 KB Output is correct
12 Correct 514 ms 20944 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 838 ms 14532 KB Output is correct
2 Correct 63 ms 9180 KB Output is correct
3 Correct 72 ms 13524 KB Output is correct
4 Correct 33 ms 10968 KB Output is correct
5 Correct 385 ms 11976 KB Output is correct
6 Correct 788 ms 14612 KB Output is correct
7 Correct 400 ms 11956 KB Output is correct
8 Correct 351 ms 11828 KB Output is correct
9 Correct 347 ms 11772 KB Output is correct
10 Correct 315 ms 11980 KB Output is correct
11 Correct 616 ms 13236 KB Output is correct
12 Correct 540 ms 13260 KB Output is correct
13 Correct 459 ms 13264 KB Output is correct
14 Correct 379 ms 12300 KB Output is correct
15 Correct 376 ms 12232 KB Output is correct
16 Correct 785 ms 14320 KB Output is correct
17 Correct 831 ms 14364 KB Output is correct
18 Correct 727 ms 14288 KB Output is correct
19 Correct 777 ms 14612 KB Output is correct
20 Correct 502 ms 13884 KB Output is correct
21 Correct 490 ms 13892 KB Output is correct
22 Correct 678 ms 14424 KB Output is correct
23 Correct 332 ms 11712 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 14644 KB Output is correct
2 Correct 682 ms 14540 KB Output is correct
3 Correct 691 ms 14924 KB Output is correct
4 Correct 698 ms 14628 KB Output is correct
5 Correct 685 ms 14800 KB Output is correct
6 Correct 972 ms 14756 KB Output is correct
7 Correct 927 ms 14480 KB Output is correct
8 Correct 871 ms 14612 KB Output is correct
9 Correct 73 ms 9204 KB Output is correct
10 Correct 641 ms 11608 KB Output is correct
11 Correct 552 ms 11984 KB Output is correct
12 Correct 426 ms 12744 KB Output is correct
13 Correct 583 ms 15868 KB Output is correct
14 Correct 707 ms 18236 KB Output is correct
15 Correct 617 ms 15080 KB Output is correct
16 Correct 891 ms 22684 KB Output is correct
17 Correct 809 ms 28092 KB Output is correct
18 Correct 71 ms 9184 KB Output is correct
19 Correct 930 ms 25352 KB Output is correct
20 Correct 752 ms 24840 KB Output is correct
21 Correct 668 ms 20684 KB Output is correct
22 Correct 525 ms 14792 KB Output is correct
23 Correct 469 ms 13912 KB Output is correct
24 Correct 599 ms 24808 KB Output is correct
25 Correct 514 ms 20944 KB Output is correct
26 Correct 935 ms 21352 KB Output is correct
27 Correct 1016 ms 18120 KB Output is correct
28 Correct 942 ms 24144 KB Output is correct
29 Correct 687 ms 17896 KB Output is correct
30 Correct 937 ms 14680 KB Output is correct
31 Correct 1040 ms 14752 KB Output is correct
32 Correct 917 ms 14964 KB Output is correct
33 Correct 836 ms 14752 KB Output is correct
34 Correct 821 ms 14724 KB Output is correct
35 Correct 889 ms 15056 KB Output is correct
36 Correct 663 ms 14544 KB Output is correct
37 Correct 748 ms 14792 KB Output is correct
38 Correct 636 ms 14800 KB Output is correct
39 Correct 458 ms 12912 KB Output is correct
40 Correct 462 ms 12992 KB Output is correct
41 Correct 437 ms 13004 KB Output is correct
42 Correct 488 ms 15824 KB Output is correct
43 Correct 524 ms 15840 KB Output is correct
44 Correct 515 ms 15820 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 34 ms 8796 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 36 ms 8788 KB Output is correct
6 Correct 29 ms 8792 KB Output is correct
7 Correct 30 ms 8796 KB Output is correct
8 Correct 34 ms 8536 KB Output is correct
9 Correct 38 ms 8764 KB Output is correct
10 Correct 33 ms 8784 KB Output is correct
11 Correct 35 ms 8540 KB Output is correct
12 Correct 38 ms 8540 KB Output is correct
13 Correct 36 ms 8788 KB Output is correct
14 Correct 36 ms 8788 KB Output is correct
15 Correct 46 ms 8768 KB Output is correct
16 Correct 38 ms 8780 KB Output is correct
17 Correct 34 ms 8780 KB Output is correct
18 Correct 705 ms 14644 KB Output is correct
19 Correct 682 ms 14540 KB Output is correct
20 Correct 691 ms 14924 KB Output is correct
21 Correct 698 ms 14628 KB Output is correct
22 Correct 685 ms 14800 KB Output is correct
23 Correct 972 ms 14756 KB Output is correct
24 Correct 927 ms 14480 KB Output is correct
25 Correct 871 ms 14612 KB Output is correct
26 Correct 73 ms 9204 KB Output is correct
27 Correct 641 ms 11608 KB Output is correct
28 Correct 552 ms 11984 KB Output is correct
29 Correct 426 ms 12744 KB Output is correct
30 Correct 583 ms 15868 KB Output is correct
31 Correct 707 ms 18236 KB Output is correct
32 Correct 617 ms 15080 KB Output is correct
33 Correct 891 ms 22684 KB Output is correct
34 Correct 809 ms 28092 KB Output is correct
35 Correct 71 ms 9184 KB Output is correct
36 Correct 930 ms 25352 KB Output is correct
37 Correct 752 ms 24840 KB Output is correct
38 Correct 668 ms 20684 KB Output is correct
39 Correct 525 ms 14792 KB Output is correct
40 Correct 469 ms 13912 KB Output is correct
41 Correct 599 ms 24808 KB Output is correct
42 Correct 514 ms 20944 KB Output is correct
43 Correct 838 ms 14532 KB Output is correct
44 Correct 63 ms 9180 KB Output is correct
45 Correct 72 ms 13524 KB Output is correct
46 Correct 33 ms 10968 KB Output is correct
47 Correct 385 ms 11976 KB Output is correct
48 Correct 788 ms 14612 KB Output is correct
49 Correct 400 ms 11956 KB Output is correct
50 Correct 351 ms 11828 KB Output is correct
51 Correct 347 ms 11772 KB Output is correct
52 Correct 315 ms 11980 KB Output is correct
53 Correct 616 ms 13236 KB Output is correct
54 Correct 540 ms 13260 KB Output is correct
55 Correct 459 ms 13264 KB Output is correct
56 Correct 379 ms 12300 KB Output is correct
57 Correct 376 ms 12232 KB Output is correct
58 Correct 785 ms 14320 KB Output is correct
59 Correct 831 ms 14364 KB Output is correct
60 Correct 727 ms 14288 KB Output is correct
61 Correct 777 ms 14612 KB Output is correct
62 Correct 502 ms 13884 KB Output is correct
63 Correct 490 ms 13892 KB Output is correct
64 Correct 678 ms 14424 KB Output is correct
65 Correct 332 ms 11712 KB Output is correct
66 Correct 935 ms 21352 KB Output is correct
67 Correct 1016 ms 18120 KB Output is correct
68 Correct 942 ms 24144 KB Output is correct
69 Correct 687 ms 17896 KB Output is correct
70 Correct 937 ms 14680 KB Output is correct
71 Correct 1040 ms 14752 KB Output is correct
72 Correct 917 ms 14964 KB Output is correct
73 Correct 836 ms 14752 KB Output is correct
74 Correct 821 ms 14724 KB Output is correct
75 Correct 889 ms 15056 KB Output is correct
76 Correct 663 ms 14544 KB Output is correct
77 Correct 748 ms 14792 KB Output is correct
78 Correct 636 ms 14800 KB Output is correct
79 Correct 458 ms 12912 KB Output is correct
80 Correct 462 ms 12992 KB Output is correct
81 Correct 437 ms 13004 KB Output is correct
82 Correct 488 ms 15824 KB Output is correct
83 Correct 524 ms 15840 KB Output is correct
84 Correct 515 ms 15820 KB Output is correct
85 Correct 1414 ms 35932 KB Output is correct
86 Correct 99 ms 13520 KB Output is correct
87 Correct 75 ms 10972 KB Output is correct
88 Correct 754 ms 12752 KB Output is correct
89 Correct 1556 ms 36092 KB Output is correct
90 Correct 765 ms 12128 KB Output is correct
91 Correct 797 ms 14632 KB Output is correct
92 Correct 783 ms 14872 KB Output is correct
93 Correct 864 ms 13824 KB Output is correct
94 Correct 1063 ms 16304 KB Output is correct
95 Correct 1059 ms 16864 KB Output is correct
96 Correct 1173 ms 15380 KB Output is correct
97 Correct 509 ms 11984 KB Output is correct
98 Correct 608 ms 12240 KB Output is correct
99 Correct 1527 ms 34396 KB Output is correct
100 Correct 1397 ms 34932 KB Output is correct
101 Correct 1374 ms 29136 KB Output is correct
102 Correct 1316 ms 29252 KB Output is correct
103 Correct 1072 ms 15540 KB Output is correct
104 Correct 1067 ms 15636 KB Output is correct
105 Correct 835 ms 16876 KB Output is correct
106 Correct 722 ms 16924 KB Output is correct
107 Correct 663 ms 14028 KB Output is correct
108 Correct 1312 ms 26828 KB Output is correct
109 Correct 815 ms 11480 KB Output is correct