Submission #332830

#	Time	Username	Problem	Language	Result	Execution time	Memory
332830		Dymo	Bridges (APIO19_bridges)	C++14	100 / 100	2458 ms	133020 KiB

bridges

#include<bits/stdc++.h>
using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e5+100;
const ll mod =1e9+7 ;
const ll base=1e18;
const ll block=1000;
/// con 1 ngay nua
/// zesitahn



struct dsu_rollback
{
    ll par[maxn];
    vector<pll> vt;
    dsu_rollback()
    {
        memset(par,-1,sizeof(par));
        vt.clear();
    }
    void rollback(ll t)
    {
        while (vt.size()>t)
        {
            auto p=vt.back();
            vt.pop_back();
            par[p.ff]=p.ss;
        }
    }
    ll find_par(ll u)
    {
        if (par[u]<0)
            return u;
        return find_par(par[u]);
    }
    void merge(ll x,ll y)
    {
        x=find_par(x);
        y=find_par(y);
        if (x==y) return ;
        if (par[x]>par[y])
        {
            swap(x,y);
        }
        vt.pb(make_pair(x,par[x]));
        vt.pb(make_pair(y,par[y]));
        par[x]+=par[y];
        par[y]=x;
    }
    bool chk(ll x,ll y)
    {
        return find_par(x)==find_par(y);
    }
};
ll w[maxn];
ll u[maxn];
ll v[maxn];
ll t[maxn];
ll a[maxn];
ll b[maxn];
ll wnw[maxn];
ll ans[maxn];
vector<ll> adj[maxn];
bool kt[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("queue.inp", "r"))
    {
        freopen("queue.inp", "r", stdin);
        freopen("queue.out", "w", stdout);
    }
    ll n, m;
     cin>> n>> m;
     for (int i=1;i<=m;i++)
     {
         cin>>u[i]>>v[i]>>w[i];
     }
     ll q;
      cin>> q;
      for (int i=1;i<=q;i++)
      {
          cin>>t[i]>>a[i]>>b[i];
      }
     for (int i=1;i<=q;i+=block)
     {
           ll l=i;
           ll r=min(i+block-1,q);
           dsu_rollback dsu;
           vector<pll> que;
           vector<ll> change;
           vector<pll> non;
           for (int j=l;j<=r;j++)
           {
               if (t[j]==1)
               {
                 kt[a[j]]=true;
                 change.pb(a[j]);
                 wnw[a[j]]=w[a[j]];
               }
           }

           for (int j=l;j<=r;j++)
           {
               if (t[j]==1)
               {
                 wnw[a[j]]=b[j];
               }
               else
               {
                  for (auto p:change)
                  {
                      if (b[j]<=wnw[p])
                      {
                         adj[j].pb(p);
                      }
                  }
                  que.pb(make_pair(b[j],j));
               }
           }
           for (int i=1;i<=m;i++)
           {
               if (!kt[i])
               {
                   non.pb(make_pair(w[i],i));
               }
           }
           sort(que.rbegin(),que.rend());
           sort(non.rbegin(),non.rend());
           ll idnw=0;
           for (auto p:que)
           {

               ll id=p.ss;
               while (idnw<non.size()&&non[idnw].ff>=p.ff)
               {
                   dsu.merge(u[non[idnw].ss],v[non[idnw].ss]);
                   idnw++;
               }
               ll siznw=dsu.vt.size();
               ll posnw=a[id];
               //cout <<p.ff<<" "<<p.ss<<" "<<posnw<<" "<<siznw<<" "<<non.size()<<endl;
               for (auto to:adj[id])
               {
                   dsu.merge(u[to],v[to]);
               }
              ans[id]=-dsu.par[dsu.find_par(posnw)];
               dsu.rollback(siznw);
           }
            for (int i=1;i<=m;i++)
           {
               if (kt[i])
               {
                   w[i]=wnw[i];
               }
               kt[i]=false;
           }
           for (int j=l;j<=r;j++)
           {
               adj[j].clear();
           }
     }
     for (int i=1;i<=q;i++)
     {
          if (t[i]==2)
          {
              cout <<ans[i]<<endl;
          }
     }


}

Compilation message (stderr)

bridges.cpp:14:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll base=1e18;
      |               ^~~~
bridges.cpp: In member function 'void dsu_rollback::rollback(int)':
bridges.cpp:32:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         while (vt.size()>t)
      |                ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |                while (idnw<non.size()&&non[idnw].ff>=p.ff)
      |                       ~~~~^~~~~~~~~~~
bridges.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         freopen("queue.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         freopen("queue.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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