Submission #948572

#	Time	Username	Problem	Language	Result	Execution time	Memory
948572		damwuan	Bridges (APIO19_bridges)	C++17	0 / 100	960 ms	13876 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef pair<db,db> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll maxk=2e5+5;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=111539786;
int n,m,q;
struct dsu_rollback
{
    int par[maxn];
    vector<pii> save;
    void init()
    {
        for1(i,1,n) par[i]=-1;
        save.clear();
    }
    int Find(int u)
    {
        return ((par[u]<0)?(u):Find(par[u]));
    }
    void Union(int u,int v)
    {
//        cerr<<"Union "<< u<< ' '<<v<<'\n';
        if ((u=Find(u))==(v=Find(v))) return;
        if (par[u]>par[v]) swap(u,v);
        save.pb({v,par[v]});
        par[u]+=par[v];
        par[v]=u;
    }
    void Roll(int x)
    {
//        cerr<< "back "<<x<<'\n';
        while (save.size()>x)
        {
            int v=save.back().fi;
            int pv=save.back().se;
            int u=par[v];
            save.pop_back();;
            par[u]-=pv;
            par[v]=pv;
        }
    }
    int Get(int u)
    {
        return par[Find(u)]*(-1);
    }
}dsu;
struct Edge
{
    int u,v,d,i;
    bool operator <(const Edge& o) const
    {
         return d>o.d;
    }
}e[maxn];
struct queri
{
    int t,s,w,s1;
    bool operator <(const queri& o) const
    {
         return w>o.w;
    }
}qr[maxn];
int x[maxn];
int ans[maxn];
vector<int> Lqr[maxn/block_sz +1][3];
int spe[maxn];
bool cc[maxn];
void sol()
{
    cin >> n>> m;
    for1(i,1,m)
    {
        int u,v,d; cin >> u>>v>>d;
        e[i]={u,v,d,i};
    }

    cin >> q;
    for1(i,1,q)
    {
        int t,s1,s,w; cin >> t>> s1>> w;
        if (t==1) s=x[s1];
        else s=s1;
        qr[i]={t,s,w,s1};

        Lqr[i/block_sz][t].pb(i);
//        cerr<<"wtf "<< i<<'\n';
    }
//    for1(i,1,m)
//    {
//        cerr<<e[i].u<<" -> "<<e[i].v<<": "<<e[i].d<<'\n';
//    }
//    for1(i,1,q)
//    {
//        cerr<< qr[i].s<<' '<<qr[i].w<<'\n';
//    }
//    return;
    for1(g,0,q/block_sz)
    {
//        sort(all(Lqr[g][1]));
//            sort(all(m))

        sort(e+1,e+1+m);
        for1(i,1,m) {x[e[i].i]=i;}
        sort(all(Lqr[g][2]),[](int x,int y)
             {
                return qr[x].w>qr[y].w;
             });
        for(int i: Lqr[g][1])
        {
            qr[i].s=x[qr[i].s1];
            spe[qr[i].s]=1;
//            cerr<< qr[i].s<<'\n';

        }
        int j=1;
        dsu.init();
//        return;
        for(int i: Lqr[g][2])
        {
//            if (g==0) cerr<< i<<'\n';
            while (j<=m && e[j].d >= qr[i].w)
            {
//                cerr<< j<<'\n';
                if (!spe[j])
                {
                    dsu.Union(e[j].u,e[j].v);
                }
                j++;
            }
//                    cerr<<"wtf "<<i<<' '<< j<<' '<<e[j].u<<' '<<e[j].v<<'\n';
            int sv=dsu.save.size();
            int moc=upper_bound(all(Lqr[g][1]),i)-Lqr[g][1].begin();
            for2(xx,moc-1,0)
            {
                int x=Lqr[g][1][xx];

                if (cc[qr[x].s]) continue;
                cc[qr[x].s]=1;
                if(qr[x].w>= qr[i].w)
                {
                    dsu.Union(e[qr[x].s].u,e[qr[x].s].v);
                }
            }
            for1(xx,moc,Lqr[g][1].size()-1)
            {
                int x=Lqr[g][1][xx];
//                if (i==5) cerr<< x<<'\n';
                if (cc[qr[x].s]) continue;
                cc[qr[x].s]=1;
                if (e[qr[x].s].d>=qr[i].w) dsu.Union(e[qr[x].s].u,e[qr[x].s].v);
            }

            for(int x: Lqr[g][1]) cc[qr[x].s]=0;
//            if (i==3) cerr<< "here\n";
//            cerr<< "asd\n";
            ans[i]=dsu.Get(qr[i].s);
//            cerr<< g<<' '<<i<<' '<<sv<<'\n';
            dsu.Roll(sv);
        }
//        cerr<< g<<'\n';
        for(int i:Lqr[g][1])
        {
            e[qr[i].s].d=qr[i].w;
            spe[qr[i].s]=0;
        }
    }
    for1(i,1,q) if (qr[i].t==2) cout << ans[i]<<'\n';



}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("F.inp","r",stdin);
//    freopen("F.out","w",stdout);

    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*
7 7
2 4 3
6 7 13
2 5 13
4 5 8
3 6 5
3 7 9
3 7 4
3
1 7 15
1 7 4
2 7 10



*/

Compilation message (stderr)

bridges.cpp: In member function 'void dsu_rollback::Roll(int)':
bridges.cpp:51:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |         while (save.size()>x)
      |                ~~~~~~~~~~~^~
bridges.cpp: In function 'void sol()':
bridges.cpp:7:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
  163 |             for1(xx,moc,Lqr[g][1].size()-1)
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:163:13: note: in expansion of macro 'for1'
  163 |             for1(xx,moc,Lqr[g][1].size()-1)
      |             ^~~~

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