Submission #402741

#	Time	Username	Problem	Language	Result	Execution time	Memory
402741		NhatMinh0208	Bridges (APIO19_bridges)	C++14	59 / 100	3032 ms	67084 KiB

bridges

/*
	Normie's Template v2.2
	Changes:
	Added modulo binpow and inverse.
*/
 
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;
 
//Pragmas (Comment out these three lines if you're submitting in szkopul.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
struct dsu
{
	int n,par[100100],h[100100],sz[100100];
    vector<pii(int)> ou[100100];
	dsu (int n)
	{
		for (int i=1;i<=n;i++)
		{
			par[i]=i;
			sz[i]=1;
			h[i]=1;
		}
		this->n=n;
	}
	
	void reset (int n)
	{
		for (int i=1;i<=n;i++)
		{
			par[i]=i;
			sz[i]=1;
			h[i]=1;
		}
		this->n=n;
	}
	int get_par(int x)
	{
		if (par[par[x]]==par[x]) return par[x];
		else return par[x]=get_par(par[x]);
	}
	int check_same(int a, int b)
	{
		return (get_par(a)==get_par(b));
	}
	int add_edge(int a, int b)
	{
		int ha=get_par(a),hb=get_par(b);
		if (ha!=hb)
		{
			if (h[ha]<h[hb])
			{
				par[ha]=hb;
				sz[hb]+=sz[ha];
			}
			else
			if (h[ha]>h[hb])
			{
				par[hb]=ha;
				sz[ha]+=sz[hb];
			}
			else
			{
				par[hb]=ha;
				sz[ha]+=sz[hb];
				h[ha]++;
			}
			return 1;
		}
		else return 0;
	}
};
dsu gr(100001);



vector<int> bounds;
vector<int> gt[100001];
int n,m,q,i,j,k,t,t1,u,v,a,b,mag;
int eu[100001],ev[100001],ew[100001],ew2[100001];
int used[100001];
int changed[100001];
int qa[100001],qb[100001],qc[100001],qr[100001];
vector<int> qw[100001];
struct cmp
{
    int operator()(int a, int b) const
    {
        if (ew[a]-ew[b])
        return (ew[a]>ew[b]);
        return (a<b);
    }
};
set<int,cmp> sett;
vector<int> qu,changes;

        auto it1=sett.begin();
        auto it2=qu.begin();
void play1()
{
 //   cout<<"play1 "<<(*it1)<<endl;
    gr.add_edge(eu[(*it1)],ev[(*it1)]);
    it1++;
    while(true)
    {
        if (it1==sett.end()) return;
        if (!changed[(*it1)]) return;
        it1++;
    }
}
    vector<int> sta,inv;
void play2()
{
 //   cout<<"play2 "<<(*it2)<<endl;
    int u,v,g,x,i,ggg;
    x=(*it2);
    for (i=0;i<changes.size();i++) 
    {
        u=gr.get_par(eu[changes[i]]);
        v=gr.get_par(ev[changes[i]]);
        if (qw[x][i]>=qc[x])
        {
        gt[u].push_back(v);
        gt[v].push_back(u);
        inv.push_back(u);
        inv.push_back(v);
        }
    }
    sta.push_back(gr.get_par(qb[x]));
    used[gr.get_par(qb[x])]=1;
    for (i=0;i<sta.size();i++)
    {
        g=sta[i];
        qr[x]+=gr.sz[g];
        for (auto gg :gt[g])
        {
            if (!used[gg])
            {
                used[gg]=1;
                sta.push_back(gg);
            }
        }
    }
    for (auto g: sta) used[g]=0;
    for (auto g: inv) gt[g].clear();
    sta.clear();
    inv.clear();
    it2++;
}

int main()
{
	fio;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>eu[i]>>ev[i]>>ew[i];
        sett.insert(i);
    }
    cin>>q;
    for (i=1;i<=q;i++)
    {
        cin>>qa[i]>>qb[i]>>qc[i];
    }
    mag=floor(sqrt(q));
    bounds.push_back(0);
    for (i=1;i*mag<q;i++) bounds.push_back(i*mag);
    bounds.push_back(q);
    for (t=1;t<bounds.size();t++)
    {
   //     cout<<"-----------------\n";
   //     cout<<"proc "<<bounds[t-1]+1<<' '<<bounds[t]<<endl;
        qu.clear();
        changes.clear();
        for (i=bounds[t-1]+1;i<=bounds[t];i++)
        {
            if (qa[i]==1) {if (!changed[qb[i]]) changes.push_back(qb[i]); changed[qb[i]]=1; }
            else qu.push_back(i);
        }
        for (auto g : changes) ew2[g]=ew[g];
        for (i=bounds[t-1]+1;i<=bounds[t];i++)
        {
            if (qa[i]==1) ew2[qb[i]]=qc[i];
            else
            {
                for (auto g : changes) qw[i].push_back(ew2[g]);
            }
        }

        gr.reset(n); 

        sort(qu.begin(),qu.end(),[](int a, int b){return (qc[a]>qc[b]);});

   //     cout<<"sett=\n";
   //     for (auto g : sett) cout<<g<<' '<<ew[g]<<' ';
   //     cout<<endl;
   //     cout<<"qu=\n";
   //     for (auto g : qu) cout<<g<<' ';
   //     cout<<endl;
   //     cout<<"changes=\n";
   //     for (auto g : changes) cout<<g<<' ';
   //     cout<<endl;

   //     cout<<"-----------------\n";
        it1=sett.begin();
        it2=qu.begin();

    while(true)
    {
        if (it1==sett.end()) break;
        if (!changed[(*it1)]) break;
        it1++;
    }
        while (it2!=qu.end())
        {
            if (it1==sett.end()) play2();

            else
            {
        //        cout<<(*it1)<<' '<<(*it2)<<endl;
            
            if (ew[(*it1)]>=qc[(*it2)]) play1();
            else play2();
            }
        }


     //   cout<<"-----------------\n";
        
        for (i=bounds[t-1]+1;i<=bounds[t];i++)
        {
            if (qa[i]==1)
            {
                changed[qb[i]]=0;
                sett.erase(qb[i]);
                ew[qb[i]]=qc[i];
                sett.insert(qb[i]);
            }
            else
            {
                qw[i].clear();
                cout<<qr[i]<<endl;
            }
        }
    }
}

Compilation message (stderr)

bridges.cpp:22: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   22 | #pragma comment(linker, "/stack:200000000")
      | 
bridges.cpp: In function 'void play2()':
bridges.cpp:202:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for (i=0;i<changes.size();i++)
      |              ~^~~~~~~~~~~~~~~
bridges.cpp:216:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for (i=0;i<sta.size();i++)
      |              ~^~~~~~~~~~~
bridges.cpp:200:19: warning: unused variable 'ggg' [-Wunused-variable]
  200 |     int u,v,g,x,i,ggg;
      |                   ^~~
bridges.cpp: In function 'int main()':
bridges.cpp:254:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |     for (t=1;t<bounds.size();t++)
      |              ~^~~~~~~~~~~~~~

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