Submission #679011

#	Time	Username	Problem	Language	Result	Execution time	Memory
679011		qwerasdfzxcl	Bridges (APIO19_bridges)	C++17	100 / 100	1976 ms	10180 KiB

bridges

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int B = 400;
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;

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;
}


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

    for (int i=1;i<=m;i++){
        scanf("%d %d %d", U+i, V+i, D+i);
        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);
    }

    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:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d %d", U+i, V+i, D+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         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