Submission #264187

#	Time	Username	Problem	Language	Result	Execution time	Memory
264187		jeqcho	Bridges (APIO19_bridges)	C++17	44 / 100	3090 ms	9576 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef int us;
typedef long long ll;
typedef pair<us,us> ii;
typedef vector<int> vi;

int C = 650;
int const M=1e5;
int const N=5e4;
int const Q=1e5;

int par[N];

void init()
{
    memset(par,-1,sizeof(par));
}

us rt(us u)
{
    if(par[u]<0) return u;
    return (par[u]=rt(par[u]));
}

void merge(us u, us v)
{
    u=rt(u); v=rt(v);
    if(u==v) return ;
   // if(par[u]==par[v]&&(rand()%2==0)) swap(u,v);
    if(par[u]>par[v]) swap(u,v);
    // par[u] must be negative, and enforcing par[u] <= par[v] ensures par[u] has bigger size
    par[u]+=par[v];
    // par[v] is now positive, and this value is used for rollback and traversing
    // par[] stores size of component for representative, stores parent for non-representative
    // if par[i] < 0, i is a representative with component size of -par[i]
    par[v]=u;
}


ii E[M];
int W[M];
int ans[Q];
pair<int,pair<int,int> > queries[Q];
vector<pair<int,pair<ii,ii> > > edges;
int n,m;

void update(int l, int r)
{
    for(int i=l;i<=r;i++)
    {
        if(queries[i].fi==1)
        {
            int lab=queries[i].se.fi; int w=queries[i].se.se;
            W[lab]=w;
        }
    }
}

bitset<N> vis;
vi adj[N];

int dfs(us u)
{
    if(vis[u])return 0;
    vis[u]=1;
    int cand = -par[u];
    for(auto v: adj[u])
    {
        cand += dfs(v);
    }
    return cand;
}

void solve(int l, int r)
{
    // vector<pair<update time or id,pair<bridge id,new weight> > > UD;
    vector<pair<int,pair<int,int> > > UD;
    // vector<id of bridge in order of updates>
    vi bad;
    vector<pair<int,pair<int,int> > > Q;
    for(int i=l;i<=r;i++) // O(sqrt(q))
    {
        if(queries[i].fi==1)
        {
            // lab is bridge id
            int lab=queries[i].se.fi; int w=queries[i].se.se;
            bad.pb(lab);
            UD.pb({i,{lab,w}});
        }
        else
        {
            int u=queries[i].se.fi; int w=queries[i].se.se;
            Q.pb({w,{u,i}});
        }
    }
    sort(Q.rbegin(),Q.rend());  // O(sqrt(q log q))
    int ptr=0;
    // start new DSU structure
    init(); // O(n)
    for(int i=0;i<Q.size();i++)// O(sqrt(q))
    {
        // process query from heaviest car
        int w=Q[i].fi; int u=Q[i].se.fi; int lab=Q[i].se.se;
        // for all bridges with ok previous weight limit
        while(ptr<edges.size()&&edges[ptr].fi>=w) // O(q+m) directly to solve(), not nested in upper for loop
        {
            // if time of last update is less than l and time of the described update is greater than r
            // i.e. this update doesn't occur during time bucket
            // i.e. no update of this bridge occurs during time bucket
            // updates before have already been committed
            // updates after time bucket is of no concern
            if(edges[ptr].se.se.fi<=l&&edges[ptr].se.se.se>=r)
                // merge the nodes mentioned in edges[ptr] with path compression
                // these will not be rolled back
                merge(edges[ptr].se.fi.fi,edges[ptr].se.fi.se); // O(log n)
            ptr++;
        }
        vector<pair<int,int> > upd;
        int pt=0;
        // for all updates in time bucket happening before the query
        while(pt<UD.size()&&UD[pt].fi<=lab) // O(sqrt(q))
        {
            int lab=UD[pt].se.fi; int w=UD[pt].se.se;
            // store state before modification
            // these states will be reverted since queries are processed offline
            upd.pb({lab,W[lab]});
            W[lab]=w;
            pt++;
        }
        // mark current version id, will rollback to this state
        // for all updates in time bucket
        // x is bridge id
        vi xtra;
        for(int x:bad) // O(sqrt(q))
        {
            int u=E[x].fi; int v=E[x].se; int ww=W[x];
            // w is car weight
            // if the updated bridge limit is ok for car
            if(w<=ww)
            {
                // here change to dfs
                int rtu = rt(u);
                int rtv = rt(v);
                adj[rtu].pb(rtv);
                adj[rtv].pb(rtu);
                xtra.pb(rtu);
                xtra.pb(rtv);
            }
        }
        int rep = rt(u);
        ans[lab] = dfs(rep);
        reverse(upd.begin(),upd.end()); // O(sqrt(q))
        for(auto t:upd) W[t.fi]=t.se; // O(sqrt(q))
        for(auto t:xtra)
        {
            adj[t].clear();
            vis[t]=0;
        }
        vis[rep]=0;
    }
    // commit all updates in time bucket
    update(l,r);    // O(sqrt(q))
}

int las[111111];
int preW[111111];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    memset(ans,-1,sizeof(ans));
    for(int i=0;i<m;i++)
    {
        int u,v,w; cin>>u>>v>>w; u--; v--;
        E[i]=mp(u,v); W[i]=preW[i]=w;
    }
    int q; cin>>q;
    int q1=0;
    for(int i=0;i<q;i++) // O(q)
    {
        int a,b,c; cin>>a>>b>>c; b--;
        if(a==1)
        {
			if(las[b]<=i-1) edges.pb({preW[b],{E[b],{las[b],i-1}}});
			las[b]=i; preW[b]=c;
		}
        queries[i]={a,{b,c}};
    }
    for(int i=0;i<m;i++) // O(m)
    {
		if(las[i]<=q-1)
		{
			edges.pb({preW[i],{E[i],{las[i],q-1}}});
		}
	}
	sort(edges.rbegin(),edges.rend()); // O( (m+q) log (m+q) )
    int l=0; int r=0;
    // O(q) loop
    // calls solve for O(sqrt(q)) times
    while(r<q)
    {
        if(queries[r].fi==1) q1++;
        // C is sqrt(n)
        if(q1>=C)
        {
            solve(l,r);
            l=r+1;
            q1=0;
        }
        r++;
    }
    if(l<q) solve(l,q-1);
    for(int i=0;i<q;i++)
    {
        if(ans[i]!=-1) cout<<ans[i]<<'\n';
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i=0;i<Q.size();i++)// O(sqrt(q))
      |                 ~^~~~~~~~~
bridges.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         while(ptr<edges.size()&&edges[ptr].fi>=w) // O(q+m) directly to solve(), not nested in upper for loop
      |               ~~~^~~~~~~~~~~~~
bridges.cpp:128:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         while(pt<UD.size()&&UD[pt].fi<=lab) // O(sqrt(q))
      |               ~~^~~~~~~~~~

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