Submission #997044

#	Time	Username	Problem	Language	Result	Execution time	Memory
997044		star	Bridges (APIO19_bridges)	C++17	100 / 100	1375 ms	23168 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define starburst ios::sync_with_stdio(0), cin.tie(0)
#define N 100005
#define B 1000
#define pb push_back
#define all(x) x.begin(),x.end()
int n, m, q;
int u[N], v[N], w[N];
int t[N], x[N], y[N];
bool changed[N];
vector<int> edge[B]; // edges should be connected
int ans[N];
//stack<int> k; // record dsu and enable rollback
int siz[N], parent[N];
vector<int> adj[N];
void reset(){
    for (int i=1;i<=n;i++){
        parent[i]=i; // every node
        siz[i]=1; // size of connected components
    }
}
inline int fiind(int x){
    if (parent[x]==x) return x;
    return parent[x]=fiind(parent[x]);
}
void join(int a, int b){
    int r1=fiind(a), r2=fiind(b);
    if (r1==r2) return;
    if (siz[r1]>siz[r2]) swap(r1,r2);
    //k.push(r1); // record the node which was joined by another
    siz[r2]+=siz[r1];
    parent[r1]=r2;
    return;
}
//void rollback(int x){
//    while (k.size()>x){ // rollback until size==x
//        int it=k.top();
//        k.pop();
//        siz[parent[it]]-=siz[it];
//        parent[it]=it;
//    }
//}
bool visited[N];
int dfs(int v){
    int d=0;
    visited[v]=1;
    for (auto u:adj[v]) if (!visited[u]) d+=dfs(u);
    return d+siz[v];
}
signed main(){
    starburst;
    cin >> n >> m;
    for (int i=1;i<=m;i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    for (int i=1;i<=q;i++) cin >> t[i] >> x[i] >> y[i];

    for (int l=1;l<=q;l+=B){ // divide into a few blocks
        int r=min(q, l+B-1); // r=l+B-1 but r should <=q
        reset();
        for (int i=1;i<=m;i++) changed[i]=0;
        vector<int> ask, upd, unchanged;
        for (int i=l;i<=r;i++){
            if (t[i]==1){ // update
                changed[x[i]]=1;
                upd.pb(i);
            }
            else ask.pb(i);
        }
        for (int i=1;i<=m;i++) if (!changed[i]) unchanged.pb(i);
        for (int i=l;i<=r;i++){
            if (t[i]==1) w[x[i]]=y[i]; // update
            else {
                edge[i-l].clear();
                for (int j:upd){
                    // join the edges which are satisfied
                    if (w[x[j]]>=y[i]) edge[i-l].pb(x[j]);
                }
            }
        }
        //sort ask by y, decreasing
        sort(all(ask), [&](int a, int b){return y[a]>y[b];});
        //sort unchanged by w, decreasing
        sort(all(unchanged), [&](int a, int b){return w[a]>w[b];});
        int now=0;
        for (int i:ask){
            while (now<unchanged.size() && w[unchanged[now]]>=y[i]){
                // join the edges
                join(u[unchanged[now]],v[unchanged[now]]);
                now++;
            }
            //int nowsiz=k.size();
            //for (int j:edge[i-l])join(u[j],v[j]);
            for (int j:edge[i-l]){
                int a=fiind(u[j]), b=fiind(v[j]);
                adj[a].pb(b), adj[b].pb(a);
            }
            int g=fiind(x[i]);
            for (int i=0;i<=n;i++) visited[i]=0;
            // count the size of connected components
            //ans[i]=siz[fiind(x[i])];
            ans[i]=dfs(g);
//            rollback(nowsiz);
            for (int j:edge[i-l]){
                adj[fiind(u[j])].clear();
                adj[fiind(v[j])].clear();
            }
        }
    }
    for (int i=1;i<=q;i++) if (t[i]==2) cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:89:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while (now<unchanged.size() && w[unchanged[now]]>=y[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