Submission #230757

#	Time	Username	Problem	Language	Result	Execution time	Memory
230757		crackersamdjam	Bridges (APIO19_bridges)	C++14	30 / 100	3088 ms	5128 KiB

bridges

#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...);}

using namespace std;
typedef pair<int, int> pii;
constexpr int MM = 1e5+5, SZ = 300;

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{
        if(id/SZ == o.id/SZ)
            return w > o.w;
        return id/SZ < o.id/SZ;
    }
    
} all[MM];

int find(int x){
    while(x != par[x])
        x = par[x];
    return x;
}

stack<pii> rm;

void merge(int x, int y, int keep){
    x = find(x), y = find(y);
    if(x == y)
        return;
    if(sz[x] > sz[y])
        swap(x, y);
    
    par[x] = y;
    sz[y] += sz[x];
    if(!keep)
        rm.emplace(x, y);
}

void pop(){
    while(rm.size()){
        int x = rm.top().first, y = rm.top().second;
        rm.pop();
        par[x] = x;
        sz[y] -= sz[x];
    }
}

void reset(){
    for(int i = 1; i <= n; i++){
        par[i] = i;
        sz[i] = 1;
    }
}

bool used[MM];

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;
    }
    sort(all, all+q);
    
    for(int i = 0; i*SZ < q; i++){
        int l = i*SZ, r = min(q, (i+1)*SZ);
        reset();
        vector<int> e, ord;
        
        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]){
                //some
                e.push_back(j);
            }
            else{
                //all
                ord.push_back(j);
            }
        }
        sort(all(ord), [](int x, int y){
            return c[x] < c[y];
        });
        
        vector<int> yes;
        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
                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 one
                set<int> done;
                
                for(int k: yes){
                    if(all[k].op == 1 and all[k].id < all[j].id){
                        int id = all[k].i;
                        if(!done.count(id) and all[k].w >= all[j].w){
                            merge(a[id], b[id], 0); //don't keep
                        }
                        done.insert(id);
                    }
                }
                // some
                for(int k: e){
                    if(!done.count(k) and c[k] >= all[j].w){
                        merge(a[k], b[k], 0);
                    }
                }
                
                ans[all[j].id] = sz[find(all[j].i)];
                
                pop();
            }
        }
        
        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: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27