oj.uz

Submission #540315

# Submission time Handle Problem Language Result Execution time Memory
540315 2022-03-20T01:36:02 Z Lobo Bridges (APIO19_bridges) C++17
100 / 100
 2786 ms 16324 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 5e4 + 10;
const int B = 800;

int n, m, q, ds[maxn], dsz[maxn], mark[maxn], a[2*maxn], b[2*maxn], d[2*maxn], ans[maxn];
int chg[2*maxn];
vector<pair<int,int>> g1[maxn], atts[2*maxn];

int find(int u) {
    if(ds[u] == u) return u;
    return find(ds[u]);
}

void join(int u, int v) {
    if(dsz[u] < dsz[v]) swap(u,v);

    dsz[u]+= dsz[v];
    ds[v] = u;
}

stack<pair<int,int>> st;
void rollback() {
    int u = st.top().fr;
    int v = st.top().sc;
    st.pop();
    if(dsz[u] < dsz[v]) swap(u,v);
    ds[v] = v;
    dsz[u]-=dsz[v];
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> d[i];
    }

    int q; cin >> q;
    for(int j = 1; j <= q; j+=B) {
        int Bq = min(B,q-j+1);

        for(int i = 1; i <= n; i++) {
            g1[i].clear();
        }

        vector<pair<pair<int,int>,int>> qrr;
        for(int i = 1; i <= m; i++) {
            atts[i].clear();
            atts[i].pb(mp(0,d[i]));
        }
        for(int i = 1; i <= Bq; i++) {
            int op; cin >> op;

            if(op == 1) {
                int id,val; cin >> id >> val;
                chg[id] = j;
                atts[id].pb(mp(i,val));
                ans[i] = -1;
            }
            else {
                int id,val; cin >> id >> val;
                qrr.pb(mp(mp(val,-id),i));
                ans[i] = 0;
            }
        }

        //coloco as arestas nao mudadas e as queries juntas e ordedo da maior pra menor
        //quando responto query com peso x ja adicionei todas as arestas nao mudadadas d[i] > x
        //para cada query eu passo por todas as att e mudo / adiciono do jeito certo

        vector<int> edgch;
        for(int i = 1; i <= m; i++) {
            if(chg[i] != j) {
                qrr.pb(mp(mp(d[i],i),0));
            }
            else {
                edgch.pb(i);
            }
        }

        sort(all(qrr),greater<pair<pair<int,int>,int>>());
        for(int i = 1; i <= n; i++) {
            ds[i] = i;
            dsz[i] = 1;
            mark[i] = 0;
        }
        for(auto X : qrr) {
            if(X.fr.sc > 0) {
                //adicionar uma aresta
                int id = X.fr.sc;
                int u = a[id];
                int v = b[id];
                // cout << " " << id << endl;
                u = find(u);
                v = find(v);
                if(u != v) join(u,v);
            }
            else {
                //sai de u com val
                int val = X.fr.fr;
                int u = -X.fr.sc;
                int idq = X.sc;
                // cout << "  " << u << " " << val << " " << idq << endl;
                int cntrll = 0;
                for(auto id : edgch) {
                    //com upperbound
                    auto it = upper_bound(all(atts[id]),mp(idq,0)); it--;
                    if(it->sc >= val) {
                        //adiciona id
                        int v1 = find(a[id]);
                        int v2 = find(b[id]);

                        if(v1 != v2) {
                            st.push(mp(v1,v2));
                            join(v1,v2);
                            cntrll++;
                        }
                    }
                }

                ans[idq] = dsz[find(u)];

                while(cntrll--) rollback();
            }
        }

        for(auto id : edgch) {
            d[id] = atts[id].back().sc;
        }

        for(int i = 1; i <= Bq; i++) {
            if(ans[i] != -1) cout << ans[i] << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 36 ms 3996 KB Output is correct
4 Correct 5 ms 3796 KB Output is correct
5 Correct 19 ms 3924 KB Output is correct
6 Correct 14 ms 3916 KB Output is correct
7 Correct 18 ms 3924 KB Output is correct
8 Correct 18 ms 3924 KB Output is correct
9 Correct 19 ms 3924 KB Output is correct
10 Correct 18 ms 3924 KB Output is correct
11 Correct 19 ms 3912 KB Output is correct
12 Correct 20 ms 3924 KB Output is correct
13 Correct 24 ms 3832 KB Output is correct
14 Correct 23 ms 3916 KB Output is correct
15 Correct 20 ms 3912 KB Output is correct
16 Correct 19 ms 3916 KB Output is correct
17 Correct 18 ms 3924 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1600 ms 8272 KB Output is correct
2 Correct 1546 ms 8276 KB Output is correct
3 Correct 1546 ms 8264 KB Output is correct
4 Correct 1518 ms 8488 KB Output is correct
5 Correct 1519 ms 8276 KB Output is correct
6 Correct 1868 ms 8588 KB Output is correct
7 Correct 1858 ms 8432 KB Output is correct
8 Correct 1903 ms 8508 KB Output is correct
9 Correct 32 ms 4052 KB Output is correct
10 Correct 1417 ms 8564 KB Output is correct
11 Correct 1478 ms 8308 KB Output is correct
12 Correct 1273 ms 8728 KB Output is correct
13 Correct 1295 ms 8224 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 7068 KB Output is correct
2 Correct 709 ms 4948 KB Output is correct
3 Correct 1240 ms 7392 KB Output is correct
4 Correct 1131 ms 7140 KB Output is correct
5 Correct 34 ms 4056 KB Output is correct
6 Correct 1221 ms 7252 KB Output is correct
7 Correct 1069 ms 7220 KB Output is correct
8 Correct 973 ms 7068 KB Output is correct
9 Correct 790 ms 7292 KB Output is correct
10 Correct 759 ms 7216 KB Output is correct
11 Correct 818 ms 6692 KB Output is correct
12 Correct 757 ms 6688 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1941 ms 11980 KB Output is correct
2 Correct 32 ms 3968 KB Output is correct
3 Correct 204 ms 10928 KB Output is correct
4 Correct 153 ms 10928 KB Output is correct
5 Correct 1951 ms 12172 KB Output is correct
6 Correct 1926 ms 12064 KB Output is correct
7 Correct 1944 ms 12040 KB Output is correct
8 Correct 974 ms 8256 KB Output is correct
9 Correct 969 ms 8272 KB Output is correct
10 Correct 964 ms 8348 KB Output is correct
11 Correct 1561 ms 10408 KB Output is correct
12 Correct 1464 ms 10316 KB Output is correct
13 Correct 1496 ms 10588 KB Output is correct
14 Correct 1725 ms 12120 KB Output is correct
15 Correct 1889 ms 11960 KB Output is correct
16 Correct 1967 ms 11848 KB Output is correct
17 Correct 1971 ms 11988 KB Output is correct
18 Correct 1974 ms 12088 KB Output is correct
19 Correct 1985 ms 11852 KB Output is correct
20 Correct 1690 ms 11324 KB Output is correct
21 Correct 1694 ms 11440 KB Output is correct
22 Correct 1865 ms 12036 KB Output is correct
23 Correct 1808 ms 10972 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1600 ms 8272 KB Output is correct
2 Correct 1546 ms 8276 KB Output is correct
3 Correct 1546 ms 8264 KB Output is correct
4 Correct 1518 ms 8488 KB Output is correct
5 Correct 1519 ms 8276 KB Output is correct
6 Correct 1868 ms 8588 KB Output is correct
7 Correct 1858 ms 8432 KB Output is correct
8 Correct 1903 ms 8508 KB Output is correct
9 Correct 32 ms 4052 KB Output is correct
10 Correct 1417 ms 8564 KB Output is correct
11 Correct 1478 ms 8308 KB Output is correct
12 Correct 1273 ms 8728 KB Output is correct
13 Correct 1295 ms 8224 KB Output is correct
14 Correct 1167 ms 7068 KB Output is correct
15 Correct 709 ms 4948 KB Output is correct
16 Correct 1240 ms 7392 KB Output is correct
17 Correct 1131 ms 7140 KB Output is correct
18 Correct 34 ms 4056 KB Output is correct
19 Correct 1221 ms 7252 KB Output is correct
20 Correct 1069 ms 7220 KB Output is correct
21 Correct 973 ms 7068 KB Output is correct
22 Correct 790 ms 7292 KB Output is correct
23 Correct 759 ms 7216 KB Output is correct
24 Correct 818 ms 6692 KB Output is correct
25 Correct 757 ms 6688 KB Output is correct
26 Correct 1580 ms 8376 KB Output is correct
27 Correct 1875 ms 8528 KB Output is correct
28 Correct 1676 ms 8412 KB Output is correct
29 Correct 1374 ms 8420 KB Output is correct
30 Correct 1958 ms 8440 KB Output is correct
31 Correct 1872 ms 8444 KB Output is correct
32 Correct 1835 ms 8568 KB Output is correct
33 Correct 1636 ms 8336 KB Output is correct
34 Correct 1697 ms 8344 KB Output is correct
35 Correct 1714 ms 8460 KB Output is correct
36 Correct 1439 ms 8420 KB Output is correct
37 Correct 1427 ms 8280 KB Output is correct
38 Correct 1371 ms 8436 KB Output is correct
39 Correct 1121 ms 8380 KB Output is correct
40 Correct 1112 ms 8472 KB Output is correct
41 Correct 1115 ms 8424 KB Output is correct
42 Correct 1217 ms 8196 KB Output is correct
43 Correct 1152 ms 8296 KB Output is correct
44 Correct 1135 ms 8424 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 36 ms 3996 KB Output is correct
4 Correct 5 ms 3796 KB Output is correct
5 Correct 19 ms 3924 KB Output is correct
6 Correct 14 ms 3916 KB Output is correct
7 Correct 18 ms 3924 KB Output is correct
8 Correct 18 ms 3924 KB Output is correct
9 Correct 19 ms 3924 KB Output is correct
10 Correct 18 ms 3924 KB Output is correct
11 Correct 19 ms 3912 KB Output is correct
12 Correct 20 ms 3924 KB Output is correct
13 Correct 24 ms 3832 KB Output is correct
14 Correct 23 ms 3916 KB Output is correct
15 Correct 20 ms 3912 KB Output is correct
16 Correct 19 ms 3916 KB Output is correct
17 Correct 18 ms 3924 KB Output is correct
18 Correct 1600 ms 8272 KB Output is correct
19 Correct 1546 ms 8276 KB Output is correct
20 Correct 1546 ms 8264 KB Output is correct
21 Correct 1518 ms 8488 KB Output is correct
22 Correct 1519 ms 8276 KB Output is correct
23 Correct 1868 ms 8588 KB Output is correct
24 Correct 1858 ms 8432 KB Output is correct
25 Correct 1903 ms 8508 KB Output is correct
26 Correct 32 ms 4052 KB Output is correct
27 Correct 1417 ms 8564 KB Output is correct
28 Correct 1478 ms 8308 KB Output is correct
29 Correct 1273 ms 8728 KB Output is correct
30 Correct 1295 ms 8224 KB Output is correct
31 Correct 1167 ms 7068 KB Output is correct
32 Correct 709 ms 4948 KB Output is correct
33 Correct 1240 ms 7392 KB Output is correct
34 Correct 1131 ms 7140 KB Output is correct
35 Correct 34 ms 4056 KB Output is correct
36 Correct 1221 ms 7252 KB Output is correct
37 Correct 1069 ms 7220 KB Output is correct
38 Correct 973 ms 7068 KB Output is correct
39 Correct 790 ms 7292 KB Output is correct
40 Correct 759 ms 7216 KB Output is correct
41 Correct 818 ms 6692 KB Output is correct
42 Correct 757 ms 6688 KB Output is correct
43 Correct 1941 ms 11980 KB Output is correct
44 Correct 32 ms 3968 KB Output is correct
45 Correct 204 ms 10928 KB Output is correct
46 Correct 153 ms 10928 KB Output is correct
47 Correct 1951 ms 12172 KB Output is correct
48 Correct 1926 ms 12064 KB Output is correct
49 Correct 1944 ms 12040 KB Output is correct
50 Correct 974 ms 8256 KB Output is correct
51 Correct 969 ms 8272 KB Output is correct
52 Correct 964 ms 8348 KB Output is correct
53 Correct 1561 ms 10408 KB Output is correct
54 Correct 1464 ms 10316 KB Output is correct
55 Correct 1496 ms 10588 KB Output is correct
56 Correct 1725 ms 12120 KB Output is correct
57 Correct 1889 ms 11960 KB Output is correct
58 Correct 1967 ms 11848 KB Output is correct
59 Correct 1971 ms 11988 KB Output is correct
60 Correct 1974 ms 12088 KB Output is correct
61 Correct 1985 ms 11852 KB Output is correct
62 Correct 1690 ms 11324 KB Output is correct
63 Correct 1694 ms 11440 KB Output is correct
64 Correct 1865 ms 12036 KB Output is correct
65 Correct 1808 ms 10972 KB Output is correct
66 Correct 1580 ms 8376 KB Output is correct
67 Correct 1875 ms 8528 KB Output is correct
68 Correct 1676 ms 8412 KB Output is correct
69 Correct 1374 ms 8420 KB Output is correct
70 Correct 1958 ms 8440 KB Output is correct
71 Correct 1872 ms 8444 KB Output is correct
72 Correct 1835 ms 8568 KB Output is correct
73 Correct 1636 ms 8336 KB Output is correct
74 Correct 1697 ms 8344 KB Output is correct
75 Correct 1714 ms 8460 KB Output is correct
76 Correct 1439 ms 8420 KB Output is correct
77 Correct 1427 ms 8280 KB Output is correct
78 Correct 1371 ms 8436 KB Output is correct
79 Correct 1121 ms 8380 KB Output is correct
80 Correct 1112 ms 8472 KB Output is correct
81 Correct 1115 ms 8424 KB Output is correct
82 Correct 1217 ms 8196 KB Output is correct
83 Correct 1152 ms 8296 KB Output is correct
84 Correct 1135 ms 8424 KB Output is correct
85 Correct 2599 ms 16324 KB Output is correct
86 Correct 261 ms 13232 KB Output is correct
87 Correct 202 ms 13308 KB Output is correct
88 Correct 2560 ms 14580 KB Output is correct
89 Correct 2639 ms 16100 KB Output is correct
90 Correct 2526 ms 14348 KB Output is correct
91 Correct 1801 ms 11148 KB Output is correct
92 Correct 1681 ms 11400 KB Output is correct
93 Correct 2204 ms 10968 KB Output is correct
94 Correct 2164 ms 13836 KB Output is correct
95 Correct 2135 ms 13928 KB Output is correct
96 Correct 2305 ms 13628 KB Output is correct
97 Correct 2119 ms 14492 KB Output is correct
98 Correct 2232 ms 14284 KB Output is correct
99 Correct 2786 ms 15880 KB Output is correct
100 Correct 2664 ms 15892 KB Output is correct
101 Correct 2743 ms 16048 KB Output is correct
102 Correct 2757 ms 15964 KB Output is correct
103 Correct 2513 ms 14640 KB Output is correct
104 Correct 2569 ms 14532 KB Output is correct
105 Correct 2013 ms 14160 KB Output is correct
106 Correct 1714 ms 13516 KB Output is correct
107 Correct 1908 ms 14596 KB Output is correct
108 Correct 2597 ms 15300 KB Output is correct
109 Correct 2471 ms 13164 KB Output is correct