oj.uz

Submission #211418

# Submission time Handle Problem Language Result Execution time Memory
211418 2020-03-20T10:15:55 Z VEGAnn Bridges (APIO19_bridges) C++14
44 / 100
 3000 ms 30784 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 = 2000;
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){ return (x == pr[x] ? x : get(pr[x])); }

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

    if (x == y) return;

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

    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]);
                    ed[lst].clear();
                }

                lst--;
            }

            int mem = sz(stk);

            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]]);

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

            while (sz(stk) > mem){
                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 12 ms 6272 KB Output is correct
2 Correct 8 ms 6272 KB Output is correct
3 Correct 55 ms 19704 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 30 ms 15224 KB Output is correct
7 Correct 23 ms 15360 KB Output is correct
8 Correct 25 ms 15360 KB Output is correct
9 Correct 26 ms 15360 KB Output is correct
10 Correct 25 ms 15360 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 34 ms 15360 KB Output is correct
13 Correct 32 ms 15744 KB Output is correct
14 Correct 30 ms 15848 KB Output is correct
15 Correct 27 ms 15360 KB Output is correct
16 Correct 24 ms 15360 KB Output is correct
17 Correct 23 ms 15360 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1888 ms 30716 KB Output is correct
2 Correct 1900 ms 30720 KB Output is correct
3 Correct 1900 ms 30784 KB Output is correct
4 Correct 1983 ms 30740 KB Output is correct
5 Correct 1992 ms 30772 KB Output is correct
6 Execution timed out 3078 ms 30612 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1657 ms 28904 KB Output is correct
2 Correct 1522 ms 26244 KB Output is correct
3 Correct 2163 ms 29080 KB Output is correct
4 Correct 1637 ms 28904 KB Output is correct
5 Correct 98 ms 8560 KB Output is correct
6 Correct 1987 ms 29020 KB Output is correct
7 Correct 1458 ms 29036 KB Output is correct
8 Correct 1210 ms 28924 KB Output is correct
9 Correct 894 ms 22248 KB Output is correct
10 Correct 756 ms 21996 KB Output is correct
11 Correct 1126 ms 29840 KB Output is correct
12 Correct 981 ms 29996 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 16488 KB Output is correct
2 Correct 80 ms 8564 KB Output is correct
3 Correct 140 ms 12144 KB Output is correct
4 Correct 68 ms 9712 KB Output is correct
5 Correct 346 ms 13932 KB Output is correct
6 Correct 1143 ms 16236 KB Output is correct
7 Correct 353 ms 13804 KB Output is correct
8 Correct 595 ms 13420 KB Output is correct
9 Correct 426 ms 13292 KB Output is correct
10 Correct 448 ms 13524 KB Output is correct
11 Correct 817 ms 14628 KB Output is correct
12 Correct 687 ms 14572 KB Output is correct
13 Correct 556 ms 14828 KB Output is correct
14 Correct 339 ms 13800 KB Output is correct
15 Correct 333 ms 13928 KB Output is correct
16 Correct 1063 ms 15852 KB Output is correct
17 Correct 1075 ms 16160 KB Output is correct
18 Correct 1073 ms 15952 KB Output is correct
19 Correct 1057 ms 15912 KB Output is correct
20 Correct 744 ms 15464 KB Output is correct
21 Correct 750 ms 15340 KB Output is correct
22 Correct 966 ms 16108 KB Output is correct
23 Correct 338 ms 12776 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1888 ms 30716 KB Output is correct
2 Correct 1900 ms 30720 KB Output is correct
3 Correct 1900 ms 30784 KB Output is correct
4 Correct 1983 ms 30740 KB Output is correct
5 Correct 1992 ms 30772 KB Output is correct
6 Execution timed out 3078 ms 30612 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6272 KB Output is correct
2 Correct 8 ms 6272 KB Output is correct
3 Correct 55 ms 19704 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 30 ms 15224 KB Output is correct
7 Correct 23 ms 15360 KB Output is correct
8 Correct 25 ms 15360 KB Output is correct
9 Correct 26 ms 15360 KB Output is correct
10 Correct 25 ms 15360 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 34 ms 15360 KB Output is correct
13 Correct 32 ms 15744 KB Output is correct
14 Correct 30 ms 15848 KB Output is correct
15 Correct 27 ms 15360 KB Output is correct
16 Correct 24 ms 15360 KB Output is correct
17 Correct 23 ms 15360 KB Output is correct
18 Correct 1888 ms 30716 KB Output is correct
19 Correct 1900 ms 30720 KB Output is correct
20 Correct 1900 ms 30784 KB Output is correct
21 Correct 1983 ms 30740 KB Output is correct
22 Correct 1992 ms 30772 KB Output is correct
23 Execution timed out 3078 ms 30612 KB Time limit exceeded
24 Halted 0 ms 0 KB -