Submission #1278911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278911		thelegendary08	Bridges (APIO19_bridges)	C++17	100 / 100	1924 ms	14372 KiB

bridges

#include<bits/stdc++.h>
// #include<atcoder/modint>
#define pb push_back
#define mp make_pair
#define rs resize
#define ft front()
#define bk back()
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define r0f(i,n) for(int i = n-1; i >= 0; i--)
#define R0F(i,k,n) for(int i = n-1; i >= k; i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
#define p2(x) (1LL << (x))
#define pct(x) (__builtin_popcountll(x))
#define ist(x,y) ((x >> y) & 1)
template<class T, class U> bool ckmin(T& a, const U& b) { return (T)b < a ? a = (T)b, 1 : 0; } 
template<class T, class U> bool ckmax(T& a, const U& b) { return a < (T)b ? a = (T)b, 1 : 0; } 
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
// using namespace atcoder; 
// using mint = modint998244353;
const int B = 1000; 
struct Edge{
	int u, v, w, id; bool operator <(const Edge &e){return w > e.w;}
};
struct Query{
	int t, a, b, id, tin; bool operator <(const Query &e){return b > e.b;}
};
struct DSU{
	vector<pair<int&, int>>his; vi par, sz; 
	DSU(int n){
		par.rs(n); sz.rs(n); f0r(i, n)par[i] = i, sz[i] = 1; 
	}
	int find(int x){
		if(x == par[x])return x; return find(par[x]); 
	}
	void unite(int a, int b, bool tmp){ 
		// out3(a,b,tmp);
		a = find(a); b = find(b); if(a == b)return; 
		if(sz[a] < sz[b])swap(a,b); 
		if(tmp)his.pb({sz[a], sz[a]}), his.pb({par[b], par[b]}); 
		sz[a] += sz[b]; par[b] = a; 
	}
	void rollback(){
		while(!his.empty()){
			his.back().first = his.back().second; his.pop_back();
		}
	}
};
int n, m; vector<Edge>s; vector<Edge>edges; vector<Query>quers;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	cin>>n>>m; f0r(i, m){in3(u,v,w); u--; v--; s.pb({u,v,w,i}); edges.pb({u,v,w,i});} int id = 0; sort(all(s));
	in(q);
	f0r(i, q){
		in3(t, a, b); a--; quers.pb({t,a,b,id,i}); if(t == 2)id++; 
	}
	vi ans(id); 
	
	for(int S = 0; S < q; S += B){
		set<int>vol; vector<Query>asks, mods; FOR(j, S, min(S+B, q))if(quers[j].t == 1)vol.insert(quers[j].a), mods.pb(quers[j]); else asks.pb(quers[j]);
		
		sort(all(asks)); int ptr = 0; DSU D = DSU(n); vb vis(m); 
		for(auto U : asks){
			// cout<<U.a<<' '<<U.b<<'\n';
			while(ptr < m && s[ptr].w >= U.b){
				if(!vol.count(s[ptr].id))D.unite(s[ptr].u, s[ptr].v, 0); ptr++;
			}
			int st = -1; 
			f0r(i, mods.size()){
				if(mods[i].tin > U.tin)break;
				if(i == mods.size() - 1 || mods[i+1].tin > U.tin){st = i; break;}
			}
			// dout(st);
			for(int i = st; i >= 0; i--){
				if(vis[mods[i].a])continue; vis[mods[i].a] = 1; 
				// dout2(mods[i].b, U.b);
				if(mods[i].b >= U.b)D.unite(edges[mods[i].a].u, edges[mods[i].a].v, 1);
			}
			for(auto x : vol){
				if(!vis[x]){
					if(edges[x].w >= U.b)D.unite(edges[x].u, edges[x].v, 1);
				}
			}
			/*
			FOR(i,st+1,mods.size()){
				if(!vis[mods[i].a])if(edges[mods[i].a].w >= U.b)D.unite(edges[mods[i].a].u, edges[mods[i].a].v, 1);
			}
			*/
			for(int i = st; i >= 0; i--){
				vis[mods[i].a] = 0; 
			}
			// dout(D.sz[D.find(U.a)]);
			ans[U.id] = D.sz[D.find(U.a)];
			// cout<<'\n';
			D.rollback(); 
		}
		FOR(j, S, min(S+B, q))if(quers[j].t == 1)edges[quers[j].a].w = quers[j].b; 
		s = edges; sort(all(s)); 
		
	}
	
	f0r(i, id)cout<<ans[i]<<'\n';
}

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