Submission #953028

#	Time	Username	Problem	Language	Result	Execution time	Memory
953028		Vladth11	Bridges (APIO19_bridges)	C++14	100 / 100	2807 ms	13084 KiB

bridges

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast") 
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
 
const ll NMAX = 50001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int BLOCK = 770;
 
int n;
 
class DSU{
public:
    int pa[NMAX * 5], sz[NMAX * 5];
    int cnt;
    struct save_dsu{
        int ra, rb, pa, pb, sza, szb;
    };
    stack <save_dsu> st;
    void init(){
        while(st.size())
            st.pop();
        cnt = n;
        for(int i = 1; i <= n; i++){
            pa[i] = i;
            sz[i] = 1;
        }
    }
    void del(){
        cnt--;
    }
    int add(){
        ++cnt;
        pa[cnt] = cnt;
        sz[cnt] = 1;
        return cnt;
    }
    int root(int a){
        if(pa[a] == a)
            return a;
        return root(pa[a]); /// hai ca vad
    }
    void merge(int a, int b){
        int ra = root(a);
        int rb = root(b);
        st.push((save_dsu){ra, rb, pa[ra], pa[rb], sz[ra], sz[rb]});
        if(ra == rb)
            return;
        if(sz[ra] < sz[rb])
            swap(ra, rb);
        pa[rb] = ra;
        sz[ra] += sz[rb];
    }
    void rollback(){
        save_dsu x = st.top();
        st.pop();
        int ra = x.ra;
        int rb = x.rb;
        pa[ra] = x.ra;
        pa[rb] = x.rb;
        sz[ra] = x.sza;
        sz[rb] = x.szb;
    }
    int szComp(int a){
        return sz[root(a)];
    }
}dsu;
 
struct edge{
    int a, b, c;
}edges[NMAX * 2], query[NMAX * 2];
 
int banned[NMAX * 2];
 
vector <pii> events;
 
bool cmp(pii a, pii b){
    int prim = 0;
    int sec = 0;
    if(a.second == 0){
        prim = query[a.first].c;
    }else{
        prim = edges[a.first].c;
    }
    if(b.second == 0){
        sec = query[b.first].c;
    }else{
        sec = edges[b.first].c;
    }
    if(prim != sec)
        return prim > sec;
    return a.second > b.second;
}
 
int f[NMAX * 2];
int sol[NMAX * 2];
 
signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int m, i, q;
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
        f[i] = -1;
    }
    cin >> q;
    for(i = 0; i < q; i++){
        cin >> query[i].a >> query[i].b >> query[i].c;
    }
    for(i = 0; i < q; i += BLOCK){
        dsu.init();
        events.clear();
        for(int j = i; j < min(q, i + BLOCK); j++){
            if(query[j].a == 1)
                banned[query[j].b] = 1;
            else
                events.push_back({j, 0});
        }
        for(int i = 1; i <= m; i++){
            if(!banned[i]){
                events.push_back({i, 1});
            }
        }
        sort(events.begin(), events.end(), cmp);
        for(auto x : events){
            if(x.second == 1){
                dsu.merge(edges[x.first].a, edges[x.first].b);
            }else{
                int cc = 0;
                for(int j = x.first - 1; j >= i; j--){
                    if(query[j].a == 1 && f[query[j].b] != x.first){
                        if(query[j].c >= query[x.first].c){
                            cc++;
                            dsu.merge(edges[query[j].b].a, edges[query[j].b].b);
                        }
                        f[query[j].b] = x.first;
                    }
                }
                for(int j = x.first + 1; j < min(q, i + BLOCK); j++){
                    if(query[j].a == 1 && f[query[j].b] != x.first){
                        if(edges[query[j].b].c >= query[x.first].c){ /// diferenta
                            cc++;
                            dsu.merge(edges[query[j].b].a, edges[query[j].b].b);
                        }
                        f[query[j].b] = x.first;
                    }
                }
                sol[x.first] = dsu.szComp(query[x.first].b);
                while(cc--){
                    dsu.rollback();
                }
            }
        }
        for(int j = i; j < min(q, i + BLOCK); j++){
            if(query[j].a == 1){
                banned[query[j].b] = 0;
                edges[query[j].b].c = query[j].c;
            }
        }
    }
    for(i = 0; i < q; i++){
        if(query[i].a == 2)
            cout << sol[i] << "\n";
    }
    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