oj.uz

Submission #211411

# Submission time Handle Problem Language Result Execution time Memory
211411 2020-03-20T10:09:51 Z VEGAnn Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 15824 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 = 100;
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 8 ms 6272 KB Output is correct
2 Correct 7 ms 6272 KB Output is correct
3 Correct 23 ms 6784 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 16 ms 6528 KB Output is correct
6 Correct 15 ms 6528 KB Output is correct
7 Correct 15 ms 6528 KB Output is correct
8 Correct 17 ms 6528 KB Output is correct
9 Correct 15 ms 6528 KB Output is correct
10 Correct 19 ms 6656 KB Output is correct
11 Correct 18 ms 6656 KB Output is correct
12 Correct 20 ms 6640 KB Output is correct
13 Correct 19 ms 6656 KB Output is correct
14 Correct 19 ms 6656 KB Output is correct
15 Correct 19 ms 6636 KB Output is correct
16 Correct 14 ms 6528 KB Output is correct
17 Correct 14 ms 6528 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 14480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 13156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 15824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 14480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6272 KB Output is correct
2 Correct 7 ms 6272 KB Output is correct
3 Correct 23 ms 6784 KB Output is correct
4 Correct 14 ms 6528 KB Output is correct
5 Correct 16 ms 6528 KB Output is correct
6 Correct 15 ms 6528 KB Output is correct
7 Correct 15 ms 6528 KB Output is correct
8 Correct 17 ms 6528 KB Output is correct
9 Correct 15 ms 6528 KB Output is correct
10 Correct 19 ms 6656 KB Output is correct
11 Correct 18 ms 6656 KB Output is correct
12 Correct 20 ms 6640 KB Output is correct
13 Correct 19 ms 6656 KB Output is correct
14 Correct 19 ms 6656 KB Output is correct
15 Correct 19 ms 6636 KB Output is correct
16 Correct 14 ms 6528 KB Output is correct
17 Correct 14 ms 6528 KB Output is correct
18 Execution timed out 3081 ms 14480 KB Time limit exceeded
19 Halted 0 ms 0 KB -