Submission #972589

#	Time	Username	Problem	Language	Result	Execution time	Memory
972589		simona1230	Bridges (APIO19_bridges)	C++17	100 / 100	2183 ms	252552 KiB

bridges

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n,m;
pair<int,int> e[100001];
int w[100001];
int q;
int t[100001],a[100001],b[100001];
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        w[i]=c;
        e[i]={x,y};
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i]>>a[i]>>b[i];
    }
}
const int block=1000;

int used[100001];
vector<int> unch,qr,upd[100001];

bool cmp1(int x,int y)
{
    return w[x]>w[y];
}
bool cmp2(int x,int y)
{
    return b[x]>b[y];
}

struct rolling
{
    int x,szx,y,szy,rnkx,rnky;
    rolling(){}
    rolling(int _x,int _szx,int rx,int _y,int _szy,int ry)
    {
        x=_x;
        szx=_szx;
        y=_y;
        szy=_szy;

        rnkx=rx;
        rnky=ry;
    }
};
stack<rolling> s;
int ans[100001],rnk[100001],par[100001],sz[100001];

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

int find_parent(int x)
{
    if(x==par[x])return x;
    return find_parent(par[x]);
}

void unite(int idx)// idx is the index of the edge in e[]
{
    int i=e[idx].first;
    int j=e[idx].second;
    i=find_parent(i);
    j=find_parent(j);

    if(i!=j)
    {
        if(rnk[i]>rnk[j])
            swap(i,j);
        s.push({i,sz[i],rnk[i],j,sz[j],rnk[j]});
        par[i]=j;
        sz[j]+=sz[i];
        if(rnk[j]==rnk[i])
            rnk[j]++;
    }
}

void rollback(int prsz)
{
    while(s.size()!=prsz)
    {
        rolling r=s.top();
        s.pop();

        par[r.x]=r.x;
        sz[r.x]=r.szx;
        par[r.y]=r.y;
        sz[r.y]=r.szy;
    }
}

void solve()
{
    for(int l=1;l<=q;l+=block)
    {
        init();
        unch.clear();// the unchanged edges' indexes
        qr.clear();// the indexes of the queries in the original order
        int r=l+block-1;

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                used[a[i]]=l;
        }

        for(int i=1;i<=m;i++)
        {
            if(used[i]!=l)
                unch.push_back(i);
        }
        sort(unch.begin(),unch.end(),cmp1);

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                w[a[i]]=b[i];

            if(t[i]==2)
            {
                qr.push_back(i);
                for(int j=l;j<=r;j++)
                    if(t[j]==1&&w[a[j]]>=b[i])
                        upd[i].push_back(a[j]);
            }
        }
        // sort queries by weight of car big to small, then add edges >=
        // from the unchanged ones and the updates
        // afterwards rollback to before the updates and go on

        sort(qr.begin(),qr.end(),cmp2);

        int j=0;
        for(int i=0;i<qr.size();i++)
        {
            int lim=b[qr[i]];
            while(j<unch.size()&&w[unch[j]]>=lim)
            {
                unite(unch[j]);
                j++;
            }

            int prsz=s.size();
            for(int j=0;j<upd[qr[i]].size();j++)
                unite(upd[qr[i]][j]);

            ans[qr[i]]=sz[find_parent(a[qr[i]])];

            rollback(prsz);
        }
    }

    for(int i=1;i<=q;i++)
        if(t[i]==2)
            cout<<ans[i]<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::stack<rolling>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     while(s.size()!=prsz)
      |           ~~~~~~~~^~~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int i=0;i<qr.size();i++)
      |                     ~^~~~~~~~~~
bridges.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while(j<unch.size()&&w[unch[j]]>=lim)
      |                   ~^~~~~~~~~~~~
bridges.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int j=0;j<upd[qr[i]].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~~

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