Submission #934063

#	Time	Username	Problem	Language	Result	Execution time	Memory
934063		vjudge1	Bridges (APIO19_bridges)	C++17	43 / 100	421 ms	15784 KiB

bridges

#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
const int N = 1e5+7;
int res[N];
vector<ii> graph[N];
struct evento{
    int peso, a,b,i;
};
vector<evento> eventos;
bool ord(evento a, evento b){
    if(a.peso == b.peso)return a.b > b.b; // las updates primero 
    return a.peso > b.peso;
}
struct dsu{
    vi pa,nh; int gru;
    dsu(int n){
        pa.resize(n+1);
        nh.resize(n+1);
        gru = n;
        fo(i,n+1){
            pa[i] = i;nh[i] = 1;
        }
    }
    int find(int i ){
        if(pa[i] == i) return i;
        return pa[i] = find(pa[i]);
    }
    void unite(int a, int b ){
        a = find(a); b = find(b);
        if(a == b)return;
        if(nh[a] < nh[b])swap(a,b);
        pa[b]=a;
        nh[a]+=nh[b];gru--;
    }
    int tam(int a ){
        return nh[find(a)];
    }
};
struct query{
    int op,a,b;
};
struct edge{
    int a,b,w;
};
edge edges[N];
bool vis[N];int ansbrute=0;
void dfs(int nodo, int peso){
    for(auto [v,w] : graph[nodo]){
        if(vis[v])continue;
        if(w<peso)continue;
        vis[v]=1;
        ansbrute++;
        dfs(v,peso);
    }
}
struct segtree{
    int st[4*N];
    void update(int nodo, int l,int r, int idx ,int val){
        if(l==r)st[nodo] = val;
        else{
            int mid = (l+r)/2;
            if(idx<=mid)update(nodo*2,l,mid,idx,val);
            else update(nodo*2+1,mid+1,r,idx,val);
            st[nodo] = min(st[nodo*2], st[nodo*2+1]);
        }
    }
    int query(int nodo, int l, int r, int i, int j ){
        if(l>j || r  <i) return 1e9+1;
        if(l>=i and r <=j)return st[nodo];
        int mid = (l+r)/2;
        return min(query(nodo*2,l,mid, i,j), query(nodo*2+1, mid+1,r,i,j));
    }
};
int main(){cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    fo(i,m){
        int a,b,w; cin >> a >> b >> w;
        eventos.pb({w,a,b,i});
        graph[a].pb({b,w});
        graph[b].pb({a,w});
        edges[i] = {a,b,w};
    }
    int q; cin >> q;
    int con = 0;
    vector<query> queries;
    fo(i,q){
        int op; cin >> op;
        if(op==2) con++;
        int nodo, peso;
        cin >> nodo >> peso;
        queries.pb({op,nodo,peso});
        eventos.pb({peso, nodo,-1,i});
    }
    if(con == q){// No hay updates
        sort(all(eventos), ord);
        dsu ami(n);
        for(auto e : eventos){
            if(e.b == -1){
                res[e.i] = ami.tam(e.a);
            }else{
                ami.unite(e.a,e.b);
            }
        }
        fo(i,q)cout << res[i] << endl;
    }else if (m==n-1){
        segtree st1;
        fo(i,m){
            st1.update(1,0,m-1,i, edges[i].w);
        }
        for(auto [op,idx, peso] : queries){
            if(op==1){
                idx--;
                st1.update(1,0,m-1,idx, peso);
            }else{idx--;
            // cout << "Pregunta" << endl;
                int l = idx, r = m-1;
                while(l<=r){
                    int mid = (l+r)/2;
                    if(st1.query(1,0,m-1,l,mid)<peso)r=mid-1;
                    else l = mid+1;
                }
                int ans = r-idx+1;
                // cout << r << endl;
                ans++;
                l=0, r = idx-1;
                while(l<=r){
                    int mid = (l+r)/2;
                    if(st1.query(1,0,m-1,mid,idx-1)< peso)l=mid+1;
                    else r = mid-1;
                }
                // cout << l << endl;
                ans += idx-l;
                cout << ans << endl;
                // cout << "FIN" << endl;
            }
            // cout << st1.query(1,0,m-1,0,m-1) << endl;
        }
    }else{
        for(auto [op,idx, peso] : queries){
            if(op == 1 ){
                idx--;
                edges[idx].w=peso;
                fo(i,n+1)graph[i].clear();
                fo(i,m){//rehacer el grafo
                    graph[edges[i].a].pb({edges[i].b,edges[i].w});
                    graph[edges[i].b].pb({edges[i].a,edges[i].w});
                }
            }else{fill(vis, vis+ n+1, 0);
                vis[idx] = 1;ansbrute=1;
                dfs(idx, peso);
                cout << ansbrute << endl;
            }
        }
    }
}

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