Submission #261341

#	Time	Username	Problem	Language	Result	Execution time	Memory
261341		rqi	Bridges (APIO19_bridges)	C++14	100 / 100	2790 ms	13596 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define ins insert
#define f first
#define s second
#define pb push_back


const int mx = 100005;
const int SQ = (sqrt(mx)*9)/3;
int n, m;
int u[mx];
int v[mx];
int d[mx];

int t[mx];
int b[mx];
int r[mx];
int s[mx];
int w[mx];
int ans[mx];
int mind[mx];

void ps(int x){
    cout << x << "\n";
}

struct DSU {
    vi e;
    void init(int n){
        e = vi(n+1, -1);
    }
    int get(int a){
        if(e[a] < 0) return a;
        e[a] = get(e[a]);
        return e[a];
    }
    int getSize(int a){
        a = get(a);
        return -e[a];
    }
    bool unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b) return 0;
        if(-e[a] < -e[b]) swap(a, b);
        e[a]+=e[b];
        e[b] = a;
        return 1;
    }

};

set<pi> eds; //weight, index
bool notinc[mx];
int cursp[mx]; //weight of special edges

void INSERT(int ind){
    eds.ins(mp(d[ind], ind));
}

void ERASE(int ind){
    eds.erase(eds.find(mp(d[ind], ind)));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> d[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> t[i];
        if(t[i] == 1){
            cin >> b[i] >> r[i];
        }
        else{
            cin >> s[i] >> w[i];
        }
    }

    
    for(int i = 1; i <= m; i++){
        INSERT(i);
    }

    for(int i = 1; i <= q; i+=SQ){
        vpi speceds; //index, original weight
        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                notinc[b[j]] = 1;
            }
        }
        for(int j = 1; j <= m; j++){ //m*q/SQ
            if(notinc[j]){
                speceds.pb(mp(j, d[j]));
            }
        }

        set<pair<pi, int>> queries;

        for(int j = i; j < i+SQ; j++){ //qlog q
            if(t[j] == 2){
                queries.ins(mp(mp(-w[j], s[j]), j));
            }
        }

        DSU bdsu;
        bdsu.init(n);

        auto it = eds.end();

        for(auto x: queries){
            int weight = -x.f.f;
            int node = x.f.s;
            int ind = x.s;
            while(it != eds.begin()){ //m*q/SQ
                pi val = *(prev(it));
                if(val.f < weight){
                    break;
                }
                it = prev(it);
                if(notinc[val.s]) continue;
                bdsu.unite(u[val.s], v[val.s]);
            }
            for(auto x: speceds){ //q*SQ
                cursp[x.f] = x.s;
            }
            for(int j = i; j < ind; j++){ //q*SQ
                if(t[j] == 1){
                    if(notinc[b[j]]){
                        cursp[b[j]] = r[j];
                    }
                }
            }


            node = bdsu.get(node);
            bool flag = 0;
            vpi seds;
            for(auto x: speceds){ //q*SQ
                if(cursp[x.f] >= weight){ 
                    seds.pb(mp(bdsu.get(u[x.f]), bdsu.get(v[x.f])));
                }
            }
            for(auto x: seds){ //q*SQ
                if(x.f == node || x.s == node){
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                ans[ind] = bdsu.getSize(node);
                continue;
            }
            DSU sdsu;
            sdsu.init(2*SQ);
            //map each relevant node
            for(auto x: seds){
                mind[x.f] = 0;
                mind[x.s] = 0;
            }
            int cnt = 0;
            for(auto x: seds){ //q*SQ*ack
                if(mind[x.f] == 0){
                    mind[x.f] = ++cnt;
                    sdsu.e[cnt] = -bdsu.getSize(x.f);
                }
                if(mind[x.s] == 0){
                    mind[x.s] = ++cnt; 
                    sdsu.e[cnt] = -bdsu.getSize(x.s);
                }
            }
            for(auto x: seds){ //q*SQ*ack
                sdsu.unite(mind[x.f], mind[x.s]);
            }
            ans[ind] = sdsu.getSize(mind[node]);
        }


        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                notinc[b[j]] = 0;
            }
        }
        //update eds
        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                ERASE(b[j]);
                d[b[j]] = r[j];
                INSERT(b[j]);
            }
        }
    }

    for(int i = 1; i <= q; i++){
        if(t[i] == 2){
            ps(ans[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