oj.uz

Submission #211422

# Submission time Handle Problem Language Result Execution time Memory
211422 2020-03-20T10:19:24 Z VEGAnn Bridges (APIO19_bridges) C++14
73 / 100
 3000 ms 24304 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pll pair<ll, ll>
#define MP make_pair
#define PB push_back
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define ft first
#define sd second
#define MP3(a,b,c) MP(MP(a,b),c)
using namespace std;
typedef long long ll;
const int N = 50100;
const int M = 100100;
const int Q = 100100;
const int CO = 200100;
const int oo = 2e9;
const int B = 1300;
const int MB = M / B + 10;
stack<pi3> stk;
vector<int> g[N], vc, ed[CO], vec, qr;
int n, m, U[M], V[M], D[M], q, ans[Q], tt = 0, mrk[M], loc[M];
int vls[B][B], tp[Q], l[Q], r[Q], siz[N], pr[N];

bool cmp(int x, int y){
    return r[x] > r[y];
}

int get(int x, bool tp){
    if (!tp)
        return (x == pr[x] ? x : pr[x] = get(pr[x], 0));
    else return (x == pr[x] ? x : get(pr[x], 1));
}

void link(int x, int y, bool tp){
    x = get(x, tp);
    y = get(y, tp);

    if (x == y) return;

    if (siz[x] < siz[y]) swap(x, y);

    if (tp) stk.push(MP3(x, y, pr[y]));
    pr[y] = x;
    siz[x] += siz[y];
}

int main(){

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#else
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i] >> D[i];
        U[i]--; V[i]--;

        g[U[i]].PB(i);
        g[V[i]].PB(i);
        vc.PB(D[i]);
    }

    cin >> q;

    for (int i = 0; i < q; i++) {
        cin >> tp[i] >> l[i] >> r[i];
        l[i]--;
        vc.PB(r[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < m; i++)
        D[i] = lower_bound(all(vc), D[i]) - vc.begin();

    for (int i = 0; i < q; i++)
        r[i] = lower_bound(all(vc), r[i]) - vc.begin();

    for (int it = 0; it < q; it += B){
        int bd = min(q, it + B);

        tt++;
        vec.clear();
        qr.clear();

        for (int i = it; i < bd; i++)
            if (tp[i] == 1) {
                if (mrk[l[i]] < tt) {
                    mrk[l[i]] = tt;
                    loc[l[i]] = sz(vec);
                    vec.PB(l[i]);
                }
            } else qr.PB(i);

        for (int i = it; i < bd; i++){
            int nm = i - it;

            if (i == it){
                for (int j = 0; j < sz(vec); j++)
                    vls[nm][j] = D[vec[j]];
            } else {
                for (int j = 0; j < sz(vec); j++)
                    vls[nm][j] = vls[nm - 1][j];
            }

            if (tp[i] == 1)
                vls[nm][loc[l[i]]] = r[i];
        }

        for (int i = 0; i < m; i++)
            if (mrk[i] < tt)
                ed[D[i]].PB(i);

        for (int i = 0; i < n; i++){
            siz[i] = 1;
            pr[i] = i;
        }

        if (sz(qr)){
            sort(all(qr), cmp);
        }

        while (sz(stk)) stk.pop();
        int lst = sz(vc) - 1;

        for (int nm : qr){
            while (lst >= 0 && lst >= r[nm]){

                if (sz(ed[lst])){
                    for (int nw : ed[lst])
                        link(U[nw], V[nw], 0);
                    ed[lst].clear();
                }

                lst--;
            }

            int gt = nm - it;

            for (int i = 0; i < sz(vec); i++)
                if (vls[gt][i] >= r[nm])
                    link(U[vec[i]], V[vec[i]], 1);

            ans[nm] = siz[get(l[nm], 1)];

            while (sz(stk) > 0){
                pi3 cr = stk.top();
                stk.pop();

                siz[cr.ft.ft] -= siz[cr.ft.sd];
                pr[cr.ft.sd] = cr.sd;
            }
        }

        while (lst >= 0){
            ed[lst].clear();
            lst--;
        }

        //end
        for (int i = 0; i < sz(vec); i++)
            D[vec[i]] = vls[bd - it - 1][i];
    }

    for (int i = 0; i < q; i++)
        if (tp[i] == 2)
            cout << ans[i] << '\n';

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB Output is correct
2 Correct 8 ms 6272 KB Output is correct
3 Correct 46 ms 13184 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 24 ms 12288 KB Output is correct
6 Correct 21 ms 12288 KB Output is correct
7 Correct 23 ms 12288 KB Output is correct
8 Correct 27 ms 12288 KB Output is correct
9 Correct 28 ms 12288 KB Output is correct
10 Correct 28 ms 12280 KB Output is correct
11 Correct 25 ms 12288 KB Output is correct
12 Correct 28 ms 12308 KB Output is correct
13 Correct 31 ms 12544 KB Output is correct
14 Correct 31 ms 12544 KB Output is correct
15 Correct 27 ms 12288 KB Output is correct
16 Correct 25 ms 12288 KB Output is correct
17 Correct 24 ms 12288 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1719 ms 21092 KB Output is correct
2 Correct 1664 ms 21276 KB Output is correct
3 Correct 1648 ms 21448 KB Output is correct
4 Correct 1757 ms 21352 KB Output is correct
5 Correct 1750 ms 21352 KB Output is correct
6 Correct 2859 ms 21608 KB Output is correct
7 Correct 2928 ms 21740 KB Output is correct
8 Correct 2871 ms 21420 KB Output is correct
9 Correct 80 ms 8564 KB Output is correct
10 Correct 1532 ms 18516 KB Output is correct
11 Correct 1379 ms 18880 KB Output is correct
12 Correct 1330 ms 20076 KB Output is correct
13 Correct 1568 ms 22376 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1328 ms 19588 KB Output is correct
2 Correct 1139 ms 17264 KB Output is correct
3 Correct 1599 ms 19816 KB Output is correct
4 Correct 1308 ms 19692 KB Output is correct
5 Correct 79 ms 8564 KB Output is correct
6 Correct 1528 ms 19688 KB Output is correct
7 Correct 1198 ms 19644 KB Output is correct
8 Correct 1018 ms 19668 KB Output is correct
9 Correct 728 ms 18028 KB Output is correct
10 Correct 622 ms 17896 KB Output is correct
11 Correct 938 ms 20676 KB Output is correct
12 Correct 817 ms 20712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 15724 KB Output is correct
2 Correct 78 ms 8564 KB Output is correct
3 Correct 143 ms 12140 KB Output is correct
4 Correct 67 ms 9712 KB Output is correct
5 Correct 401 ms 13420 KB Output is correct
6 Correct 1330 ms 15720 KB Output is correct
7 Correct 398 ms 13416 KB Output is correct
8 Correct 585 ms 12904 KB Output is correct
9 Correct 568 ms 12776 KB Output is correct
10 Correct 522 ms 12940 KB Output is correct
11 Correct 966 ms 14056 KB Output is correct
12 Correct 977 ms 13932 KB Output is correct
13 Correct 791 ms 14472 KB Output is correct
14 Correct 393 ms 13544 KB Output is correct
15 Correct 389 ms 13548 KB Output is correct
16 Correct 1328 ms 15340 KB Output is correct
17 Correct 1339 ms 15496 KB Output is correct
18 Correct 1343 ms 15208 KB Output is correct
19 Correct 1332 ms 15468 KB Output is correct
20 Correct 890 ms 14700 KB Output is correct
21 Correct 894 ms 14892 KB Output is correct
22 Correct 1169 ms 15484 KB Output is correct
23 Correct 432 ms 12328 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1719 ms 21092 KB Output is correct
2 Correct 1664 ms 21276 KB Output is correct
3 Correct 1648 ms 21448 KB Output is correct
4 Correct 1757 ms 21352 KB Output is correct
5 Correct 1750 ms 21352 KB Output is correct
6 Correct 2859 ms 21608 KB Output is correct
7 Correct 2928 ms 21740 KB Output is correct
8 Correct 2871 ms 21420 KB Output is correct
9 Correct 80 ms 8564 KB Output is correct
10 Correct 1532 ms 18516 KB Output is correct
11 Correct 1379 ms 18880 KB Output is correct
12 Correct 1330 ms 20076 KB Output is correct
13 Correct 1568 ms 22376 KB Output is correct
14 Correct 1328 ms 19588 KB Output is correct
15 Correct 1139 ms 17264 KB Output is correct
16 Correct 1599 ms 19816 KB Output is correct
17 Correct 1308 ms 19692 KB Output is correct
18 Correct 79 ms 8564 KB Output is correct
19 Correct 1528 ms 19688 KB Output is correct
20 Correct 1198 ms 19644 KB Output is correct
21 Correct 1018 ms 19668 KB Output is correct
22 Correct 728 ms 18028 KB Output is correct
23 Correct 622 ms 17896 KB Output is correct
24 Correct 938 ms 20676 KB Output is correct
25 Correct 817 ms 20712 KB Output is correct
26 Correct 1585 ms 21480 KB Output is correct
27 Correct 2098 ms 21484 KB Output is correct
28 Correct 1704 ms 21352 KB Output is correct
29 Correct 1128 ms 21356 KB Output is correct
30 Correct 2151 ms 21108 KB Output is correct
31 Correct 2287 ms 21184 KB Output is correct
32 Correct 2278 ms 21224 KB Output is correct
33 Correct 1898 ms 21168 KB Output is correct
34 Correct 1895 ms 21232 KB Output is correct
35 Correct 1917 ms 21268 KB Output is correct
36 Correct 1363 ms 21160 KB Output is correct
37 Correct 1334 ms 21128 KB Output is correct
38 Correct 1284 ms 21072 KB Output is correct
39 Correct 894 ms 19436 KB Output is correct
40 Correct 853 ms 19372 KB Output is correct
41 Correct 868 ms 19568 KB Output is correct
42 Correct 1111 ms 22204 KB Output is correct
43 Correct 1101 ms 22352 KB Output is correct
44 Correct 1093 ms 22464 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB Output is correct
2 Correct 8 ms 6272 KB Output is correct
3 Correct 46 ms 13184 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 24 ms 12288 KB Output is correct
6 Correct 21 ms 12288 KB Output is correct
7 Correct 23 ms 12288 KB Output is correct
8 Correct 27 ms 12288 KB Output is correct
9 Correct 28 ms 12288 KB Output is correct
10 Correct 28 ms 12280 KB Output is correct
11 Correct 25 ms 12288 KB Output is correct
12 Correct 28 ms 12308 KB Output is correct
13 Correct 31 ms 12544 KB Output is correct
14 Correct 31 ms 12544 KB Output is correct
15 Correct 27 ms 12288 KB Output is correct
16 Correct 25 ms 12288 KB Output is correct
17 Correct 24 ms 12288 KB Output is correct
18 Correct 1719 ms 21092 KB Output is correct
19 Correct 1664 ms 21276 KB Output is correct
20 Correct 1648 ms 21448 KB Output is correct
21 Correct 1757 ms 21352 KB Output is correct
22 Correct 1750 ms 21352 KB Output is correct
23 Correct 2859 ms 21608 KB Output is correct
24 Correct 2928 ms 21740 KB Output is correct
25 Correct 2871 ms 21420 KB Output is correct
26 Correct 80 ms 8564 KB Output is correct
27 Correct 1532 ms 18516 KB Output is correct
28 Correct 1379 ms 18880 KB Output is correct
29 Correct 1330 ms 20076 KB Output is correct
30 Correct 1568 ms 22376 KB Output is correct
31 Correct 1328 ms 19588 KB Output is correct
32 Correct 1139 ms 17264 KB Output is correct
33 Correct 1599 ms 19816 KB Output is correct
34 Correct 1308 ms 19692 KB Output is correct
35 Correct 79 ms 8564 KB Output is correct
36 Correct 1528 ms 19688 KB Output is correct
37 Correct 1198 ms 19644 KB Output is correct
38 Correct 1018 ms 19668 KB Output is correct
39 Correct 728 ms 18028 KB Output is correct
40 Correct 622 ms 17896 KB Output is correct
41 Correct 938 ms 20676 KB Output is correct
42 Correct 817 ms 20712 KB Output is correct
43 Correct 1356 ms 15724 KB Output is correct
44 Correct 78 ms 8564 KB Output is correct
45 Correct 143 ms 12140 KB Output is correct
46 Correct 67 ms 9712 KB Output is correct
47 Correct 401 ms 13420 KB Output is correct
48 Correct 1330 ms 15720 KB Output is correct
49 Correct 398 ms 13416 KB Output is correct
50 Correct 585 ms 12904 KB Output is correct
51 Correct 568 ms 12776 KB Output is correct
52 Correct 522 ms 12940 KB Output is correct
53 Correct 966 ms 14056 KB Output is correct
54 Correct 977 ms 13932 KB Output is correct
55 Correct 791 ms 14472 KB Output is correct
56 Correct 393 ms 13544 KB Output is correct
57 Correct 389 ms 13548 KB Output is correct
58 Correct 1328 ms 15340 KB Output is correct
59 Correct 1339 ms 15496 KB Output is correct
60 Correct 1343 ms 15208 KB Output is correct
61 Correct 1332 ms 15468 KB Output is correct
62 Correct 890 ms 14700 KB Output is correct
63 Correct 894 ms 14892 KB Output is correct
64 Correct 1169 ms 15484 KB Output is correct
65 Correct 432 ms 12328 KB Output is correct
66 Correct 1585 ms 21480 KB Output is correct
67 Correct 2098 ms 21484 KB Output is correct
68 Correct 1704 ms 21352 KB Output is correct
69 Correct 1128 ms 21356 KB Output is correct
70 Correct 2151 ms 21108 KB Output is correct
71 Correct 2287 ms 21184 KB Output is correct
72 Correct 2278 ms 21224 KB Output is correct
73 Correct 1898 ms 21168 KB Output is correct
74 Correct 1895 ms 21232 KB Output is correct
75 Correct 1917 ms 21268 KB Output is correct
76 Correct 1363 ms 21160 KB Output is correct
77 Correct 1334 ms 21128 KB Output is correct
78 Correct 1284 ms 21072 KB Output is correct
79 Correct 894 ms 19436 KB Output is correct
80 Correct 853 ms 19372 KB Output is correct
81 Correct 868 ms 19568 KB Output is correct
82 Correct 1111 ms 22204 KB Output is correct
83 Correct 1101 ms 22352 KB Output is correct
84 Correct 1093 ms 22464 KB Output is correct
85 Correct 2341 ms 24216 KB Output is correct
86 Correct 214 ms 19568 KB Output is correct
87 Correct 120 ms 17136 KB Output is correct
88 Correct 1042 ms 20624 KB Output is correct
89 Correct 2410 ms 24304 KB Output is correct
90 Correct 1064 ms 20332 KB Output is correct
91 Correct 1959 ms 21064 KB Output is correct
92 Correct 2017 ms 21116 KB Output is correct
93 Execution timed out 3067 ms 21088 KB Time limit exceeded
94 Halted 0 ms 0 KB -