Submission #1044744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044744		ihceker	Bridges (APIO19_bridges)	C++14	27 / 100	3062 ms	46544 KiB

bridges

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

struct SegmentTree{
	vector<int>st;
	SegmentTree(int N){
		st.resize(4*N+5);
	}
	inline void update(int node,int l,int r,int x,int y){
		if(l>x || r<x)return;
		if(l==r){
			st[node]=y;
			return;
		}
		int mid=(l+r)/2;
		update(node*2,l,mid,x,y);
		update(node*2+1,mid+1,r,x,y);
		st[node]=min(st[node*2],st[node*2+1]);
		return;
	}
	inline int query(int node,int l,int r,int x,int y){
		if(l>y || r<x || r<l)return 1e15;
		if(l>=x && r<=y)return st[node];
		int mid=(l+r)/2;
		return min(query(node*2,l,mid,x,y),query(node*2+1,mid+1,r,x,y));
	}
};

int32_t main(){
	fast;
	int n,m;
	cin>>n>>m;
	vector<pair<int,pair<int,int>>>edges,edge(m);
	for(int i=0;i<m;i++){
		int u,v,d;
		cin>>u>>v>>d;
		u--,v--;
		edges.pb({d,{u,v}});
		edge[i]={d,{u,v}};
	}
	auto find_mst=[&](vector<pair<int,pair<int,int>>>&edges,vector<vector<pair<int,int>>>&adj,vector<vector<pair<int,int>>>&par,vector<int>&sub)->void{
		for(int i=0;i<n;i++){
			adj[i].clear();
		}
		sort(all(edges),[](pair<int,pair<int,int>>&a,pair<int,pair<int,int>>&b){return a.ff>b.ff;});
		vector<int>fa(n),id(n);
		for(int i=0;i<n;i++){
			fa[i]=i;
			id[i]=i;
			sub[i]=1;
		}
		int cnt=n;
		auto find=[&](int x,auto&& find)->int{
			if(fa[x]==x)return x;
			return fa[x]=find(fa[x],find);
		};
		auto merge=[&](int x,int y,int z)->bool{
			int a=find(x,find),b=find(y,find);
			if(a==b)return false;
			par[cnt][0]={-1,-1};
			par[id[a]][0]={z,cnt};
			par[id[b]][0]={z,cnt};
			sub[cnt]=sub[id[a]]+sub[id[b]];
			fa[a]=b;
			id[b]=cnt;
			cnt++;
			return true;
		};
		for(auto i:edges){
			if(merge(i.ss.ff,i.ss.ss,i.ff)){
				adj[i.ss.ff].pb({i.ss.ss,i.ff});
				adj[i.ss.ss].pb({i.ss.ff,i.ff});
			}
		}
		return;
	};
	int l=__lg(2*n)+1;
	vector<vector<pair<int,int>>>adj(n),par(2*n,vector<pair<int,int>>(l));
	vector<int>sub(2*n);
	find_mst(edges,adj,par,sub);
	for(int j=1;j<l;j++){
		for(int i=0;i<2*n-1;i++){
			if(par[i][j-1].ss==-1)par[i][j]={-1,-1};
			else{
				par[i][j].ff=min(par[i][j-1].ff,par[par[i][j-1].ss][j-1].ff);
				par[i][j].ss=par[par[i][j-1].ss][j-1].ss;
			}
		}
	}
	int q;
	cin>>q;
	bool subtask=true;
	vector<pair<int,pair<int,int>>>queries;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			subtask=false;
			int b,r;
			cin>>b>>r;
			b--;
			queries.pb({t,{b,r}});
		}
		else{
			int s,w;
			cin>>s>>w;
			s--;
			queries.pb({t,{s,w}});
		}
	}
	bool is_chain=true;
	is_chain&=(m==n-1);
	for(int i=0;i<m;i++){
		is_chain&=(edge[i].ss.ff==i+1 && edge[i].ss.ss==i+2);
	}
	if(subtask){
		for(auto i:queries){
			int s=i.ss.ff,w=i.ss.ss;
			for(int i=l-1;i>=0;i--){
				if(par[s][i].ss!=-1 && par[s][i].ff>=w){
					s=par[s][i].ss;
				}
			}
			cout<<sub[s]<<'\n';
		}
	}
	else if(is_chain){
		if(n==1){
			for(auto i:queries){
				if(i.ff==2){
					cout<<1<<'\n';
				}
			}
			return 0;
		}
		SegmentTree st(n-1);
		for(int i=0;i<n-1;i++){
			st.update(1,1,n-1,i+1,edge[i].ff);
		}
		for(auto i:queries){
			if(i.ff==1){
				st.update(1,1,n-1,i.ss.ff+1,i.ss.ss);
			}
			else{
				int l=i.ss.ff+2,r=n;
				while(l<=r){
					int mid=(l+r)/2;
					if(st.query(1,1,n-1,i.ss.ff+1,mid-1)>=i.ss.ss)l=mid+1;
					else r=mid-1;
				}
				int ans=r-(i.ss.ff+1);
				l=1,r=i.ss.ff;
				while(l<=r){
					int mid=(l+r)/2;
					if(st.query(1,1,n-1,mid,i.ss.ff)>=i.ss.ss)r=mid-1;
					else l=mid+1;
				}
				ans+=i.ss.ff+1-l;
				cout<<ans+1<<'\n';
			}
		}
	}
	else{
		for(auto i:queries){
			int t=i.ff;
			if(t==1){
				int b=i.ss.ff,r=i.ss.ss;
				int ind=find(all(edges),edge[b])-edges.begin();
				edges[ind].ff=r;
				edge[b].ff=r;
				find_mst(edges,adj,par,sub);
			}
			else{
				int s=i.ss.ff,w=i.ss.ss;
				int ans=0;
				auto dfs=[&](int node,int p,auto&& dfs)->void{
					ans++;
					for(auto i:adj[node]){
						if(i.ss<w || i.ff==p)continue;
						dfs(i.ff,node,dfs);
					}
					return;
				};
				dfs(s,-1,dfs);
				cout<<ans<<'\n';
			}
		}
	}
}

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