Submission #230761

#	Time	Username	Problem	Language	Result	Execution time	Memory
230761		crackersamdjam	Bridges (APIO19_bridges)	C++14	100 / 100	2596 ms	8688 KiB

bridges

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

constexpr int MM = 1e5+5, SZ = 800;

int n, m, q, a[MM], b[MM], c[MM], ans[MM], par[MM], sz[MM];

struct st{
    int op, i, w, id;
    bool operator<(const st &o) const{
        return w > o.w;
    }
    
} all[MM];

inline int find(int x){
    while(x != par[x])
        x = par[x];
    return x;
}
std::vector<std::pair<int, int>> rm;
inline void merge(int x, int y, int keep){
    x = find(x), y = find(y);
    if(x == y)
        return;
    if(sz[x] > sz[y]){
        int z = x;
        x = y;
        y = z;
    }
    par[x] = y;
    sz[y] += sz[x];
    if(!keep)
        rm.emplace_back(x, y);
}
inline void pop(){
    while(rm.size()){
        int x = rm.back().first, y = rm.back().second;
        rm.pop_back();
        par[x] = x;
        sz[y] -= sz[x];
    }
}
inline void reset_dsu(){
    for(int i = 1; i <= n; i++){
        par[i] = i;
        sz[i] = 1;
    }
}

std::vector<int> e, ord, rmdone, yes;
bool used[MM], done[MM];
//used in this group, done in this group

int main(){
    memset(ans, -1, sizeof ans);
    scan(n, m);
    for(int i = 1; i <= m; i++){
        scan(a[i], b[i], c[i]);
    }
    scan(q);
    for(int i = 0; i < q; i++){
        scan(all[i].op, all[i].i, all[i].w);
        all[i].id = i;
    }
    
    for(int i = 0; i*SZ < q; i++){
        int l = i*SZ, r = (i+1)*SZ;
        if(r > q)
            r = q;
        std::sort(all+l, all+r);
        reset_dsu();
        e.clear();
        ord.clear();
        for(int j = l; j < r; j++){
            if(all[j].op == 1)
                used[all[j].i] = 1;
        }
        
        //loop edges (each one only once)
        for(int j = 1; j <= m; j++){
            if(used[j]) e.push_back(j); //some
            else ord.push_back(j); //all
        }
        sort(all(ord), [](int x, int y){
            return c[x] < c[y];
        });
        
        yes.clear();
        for(int j = l; j < r; j++)
            yes.emplace_back(j);
        sort(all(yes), [](int x, int y){
            return all[x].id > all[y].id;
        });
        
        //already sorted by greatest w
        for(int j = l; j < r; j++){
            if(all[j].op == 2){
                //all (prev groups)
                while(ord.size() and c[ord.back()] >= all[j].w){
                    int id = ord.back(); ord.pop_back();
                    merge(a[id], b[id], 1);
                }
                //specific to this group
                for(int k: yes){
                    if(all[k].op == 1 and all[k].id < all[j].id){
                        int id = all[k].i;
                        if(!done[id]){
                            if(all[k].w >= all[j].w)
                                merge(a[id], b[id], 0);
                            done[id] = 1;
                            rmdone.emplace_back(id);
                        }
                    }
                }
                //some (prev groups)
                for(int k: e){
                    if(!done[k] and c[k] >= all[j].w)
                        merge(a[k], b[k], 0);
                }
                
                ans[all[j].id] = sz[find(all[j].i)];
                
                pop();
                while(rmdone.size()){
                    done[rmdone.back()] = 0;
                    rmdone.pop_back();
                }
            }
        }
        
        reverse(all(yes));
        for(int j: yes){
            if(all[j].op == 1){
                used[all[j].i] = 0;
                c[all[j].i] = all[j].w;
                //update for future batches
            }
        }
    }
    
    for(int i = 0; i < q; i++){
        if(~ans[i])
            print(ans[i]);
    }
    
    return 0;
}

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