Submission #927299

#	Time	Username	Problem	Language	Result	Execution time	Memory
927299		Dzadzo	Bridges (APIO19_bridges)	C++17	14 / 100	228 ms	524288 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 100000
using namespace std;
int p[MAXN+1];
int s[MAXN+1];
stack <pair<pii,int>> st;
int find(int v){
	if (p[v]==v)return v;
	return find(p[v]);
}
void unite(int v,int u){
	v=find(v);
	u=find(u);
	if (s[u]>s[v])swap(u,v);
	st.push({{u,v},p[u]});
	p[u]=v;
	s[v]+=s[u];
}
void rollback(){
	int u=st.top().F.F;
	int v=st.top().F.S;
	int pu=st.top().S;
	p[u]=pu;
	s[v]-=s[u];
	st.pop();
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vector<pair<pii,pii>> edges;
	int V[m+1],U[m+1],W[m+1];
	for (int i=1;i<=m;i++){
		cin>>U[i]>>V[i]>>W[i];
		edges.pb({{W[i],i},{U[i],V[i]}});
	}
	sort(edges.rbegin(),edges.rend());
	edges.pb({{0,0},{0,0}});
	int q;
	cin>>q;
	int B=INF;
	vp temp[q+1];
	vector<pair<pii,int>> Q;
	int cur=0;
	vi res(q+1);
	vb marked(m+2);
	for (int tt=1;tt<=q;tt++){
		int tp,x,y;
		cin>>tp>>x>>y;
		temp[tt]=temp[tt-1];
		if (tp==1){
			temp[tt].pb({x,y});
		}else{
			Q.pb({{y,x},tt});
		}
		cur++;
		if (cur==B || tt==q){
			Q.pb({{0,0},0});
			sort(Q.rbegin(),Q.rend());
			int l=0;
			for (auto &[id,c]:temp[tt])marked[id]=true;
			while (st.size())st.pop();
			for (int i=1;i<=n;i++)s[i]=1,p[i]=i;
			for (auto z:edges){
				int w=z.F.F;
				int ind=z.F.S;
				int u=z.S.F;
				int v=z.S.S;
				if (marked[ind])continue;
				while (w<Q[l].F.F){
					int cnt=0;
					for (auto k:temp[Q[l].S]){
						marked[k.F]=false;
						if (k.S>=Q[l].F.F && find(U[k.F])!=find(V[k.F]))unite(U[k.F],V[k.F]),cnt++;
					}
					for (auto k:temp[tt]){
						if (!marked[k.F])continue;
						if (W[k.F]>=Q[l].F.F &&find(U[k.F])!=find(V[k.F]))unite(U[k.F],V[k.F]),cnt++;						
					}
					for (auto k:temp[Q[l].S])marked[k.F]=true;					
					res[Q[l].S]=s[find(Q[l].F.S)];
					while (cnt--)rollback();
					l++;
				}
				if (find(u)!=find(v))unite(u,v);
			}
			for (auto [id,c]:temp[tt])marked[id]=false;
			temp[tt].clear();
			cur=0;
		}
	}
	for (int i=1;i<=q;i++)if (res[i])cout<<res[i]<<"\n";
}

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