Submission #679025

#	Time	Username	Problem	Language	Result	Execution time	Memory
679025		qwerasdfzxcl	Bridges (APIO19_bridges)	C++17	100 / 100	1392 ms	6532 KiB

bridges

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int B = 369;
struct DSU{
    int path[50050], sz[50050];
    vector<pair<int, int>> mylog;

    void init(int n){mylog.clear(); for (int i=1;i<=n;i++) path[i] = i, sz[i] = 1;}

    int find(int s){
        if (s==path[s]) return s;
        return find(path[s]);
    }
    bool merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return 0;
        if (sz[s] > sz[v]) swap(s, v);

        mylog.emplace_back(s, sz[s]);
        path[s] = v;
        sz[v] += sz[s];
        return 1;
    }
    int size(int s){return sz[find(s)];}
    void rollback(int c){
        for (int z=0;z<c;z++){
            auto [s, _sz] = mylog.back(); mylog.pop_back();
            sz[path[s]] -= _sz;
            path[s] = s;
        }
    }
}dsu;


struct Seg{
    int tree[100100], sz;
    void init(int n, int a[]){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    int query(int l, int r){
        ++r;
        int ret = 1e9;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}tree;

int U[100100], V[100100], D[100100], op[100100], qa[100100], qb[100100], uc[100100], ans[100100], chk[100100];

bool cmp(int i, int j){return D[i] > D[j];}
bool cmp2(int i, int j){
    if (uc[i]/B == uc[j]/B){
        if (op[i]==op[j]){
            if (op[i]==1) return uc[i] < uc[j];
            return qb[i] > qb[j];
        }
        return op[i] < op[j];
    }
    return uc[i]/B < uc[j]/B;
}

void solve_subtask2(int n, int m, int q){
    tree.init(m+1, D);
    for (int i=1;i<=q;i++){
        if (op[i]==1) tree.update(qa[i], qb[i]);
        else{
            int L = qa[i], R = qa[i];

            int tl = 1, tr = qa[i] - 1;
            while(tl<=tr){
                int tm = (tl+tr)>>1;
                if (tree.query(tm, qa[i]-1) >= qb[i]) L = tm, tr = tm-1;
                else tl = tm+1;
            }

            tl = qa[i], tr = m;
            while(tl<=tr){
                int tm = (tl+tr)>>1;
                if (tree.query(qa[i], tm) >= qb[i]) R = tm+1, tl = tm+1;
                else tr = tm-1;
            }

            printf("%d\n", R-L+1);
        }
    }
    exit(0);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> I, qI;

    bool subtask2 = true;
    for (int i=1;i<=m;i++){
        scanf("%d %d %d", U+i, V+i, D+i);
        if (m!=n-1 || U[i]!=i || V[i]!=i+1) subtask2 = false;
        I.push_back(i);
    }

    int q;
    scanf("%d", &q);
    for (int i=1;i<=q;i++){
        scanf("%d %d %d", op+i, qa+i, qb+i);
        uc[i] = uc[i-1] + (op[i]==1);
        qI.push_back(i);
    }

    if (subtask2) solve_subtask2(n, m, q);

    sort(I.begin(), I.end(), cmp);
    sort(qI.begin(), qI.end(), cmp2);

    for (int i=0;i<q;){
        int r = i, r2 = i;
        while(r<q && uc[qI[i]]/B == uc[qI[r]]/B) ++r;
        while(r2<q && op[qI[r2]]==1){
            chk[qa[qI[r2]]] = D[qa[qI[r2]]];
            ++r2;
        }

        dsu.init(n);
        int pt = 0;
        for (int j=r2;j<r;j++){
            assert(op[qI[j]]==2);
            while(pt < m && qb[qI[j]] <= D[I[pt]]){
                if (chk[I[pt]]) {++pt; continue;}
                dsu.merge(U[I[pt]], V[I[pt]]);
                ++pt;
            }

            for (int k=i;k<r2;k++){
                if (uc[qI[k]] > uc[qI[j]]) break;
                chk[qa[qI[k]]] = qb[qI[k]];
            }

            int cnt = 0;
            for (int k=i;k<r2;k++){
                if (chk[qa[qI[k]]] >= qb[qI[j]]){
                    if (dsu.merge(U[qa[qI[k]]], V[qa[qI[k]]])) cnt++;
                }
            }

            for (int k=i;k<r2;k++){
                if (uc[qI[k]] > uc[qI[j]]) break;
                chk[qa[qI[k]]] = D[qa[qI[k]]];
            }

            ans[qI[j]] = dsu.size(qa[qI[j]]);
            //printf("ok ans[%d] = %d\n", qI[j], ans[qI[j]]);

            dsu.rollback(cnt);
        }

        vector<int> I1, I2;
        for (auto &x:I){
            if (chk[x]){
                I2.push_back(x);
                chk[x] = 0;
            }
            else I1.push_back(x);
        }

        for (int j=i;j<r2;j++) D[qa[qI[j]]] = qb[qI[j]];
        sort(I2.begin(), I2.end(), cmp);
        merge(I1.begin(), I1.end(), I2.begin(), I2.end(), I.begin(), cmp);

        i = r;
    }

    for (int i=1;i<=q;i++) if (op[i]==2) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d %d %d", U+i, V+i, D+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d %d %d", op+i, qa+i, qb+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27