Submission #446139

#	Time	Username	Problem	Language	Result	Execution time	Memory
446139		Millad	Bridges (APIO19_bridges)	C++14	100 / 100	2878 ms	131624 KiB

bridges

//In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cout << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll sq = 1000;
ll n, m, q, w[maxn], a[maxn], b[maxn], t[maxn], x[maxn], y[maxn];
ll sz[maxn], par[maxn], ans[maxn];
stack <ll> his;
vector <ll> mrge[maxn];
bool cng[maxn];
bool cmp(ll i, ll j){
	return(y[i] > y[j]);
}
bool cmp2(ll i, ll j){
	return(w[i] > w[j]);
}
ll get(ll v){
	if(v == par[v])return v;
	return get(par[v]);
}
void mrg(ll ind){
	ll v = get(a[ind]), u = get(b[ind]);
	if(v == u)return;
	if(sz[v] > sz[u])swap(u, v);
	par[v] = u;
	sz[u] += sz[v];
	his.push(v);
}
void roll_back(){
	ll v = his.top();
	his.pop();
	sz[par[v]] -= sz[v];
	par[v] = v;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(ll i = 1; i <= m; i ++){
		cin >> a[i] >> b[i] >> w[i];
	}
	cin >> q;
	for(ll i = 1; i <= q; i ++){
		cin >> t[i] >> x[i] >> y[i];
	}
	for(ll l = 1; l <= q; l += sq){
		ll r = min(q + 1, l + sq);
		for(ll i = 1; i <= n; i ++){
			par[i] = i;
			sz[i] = 1;
		}
		memset(cng, 0, sizeof cng);
		vector <ll> up, ask, vec;
		for(ll i = l; i < r; i ++){
			if(t[i] == 1){
				up.pb(i);
				cng[x[i]] = 1;
			}
			else{
				ask.pb(i);
			}
		}
		for(ll i = 1; i <= m; i ++){
			if(cng[i])continue;
			vec.pb(i);
		}
		sort(ask.begin(), ask.end(), cmp);
		sort(vec.begin(), vec.end(), cmp2);
		for(ll i = l; i < r; i ++){
			if(t[i] == 1){
				w[x[i]] = y[i];
			}
			else{
				for(ll j : up){
					if(w[x[j]] >= y[i]){
						mrge[i].pb(x[j]);
					}
				}
			}
		}
		ll ind = 0;
		for(ll v : ask){
			while((ind < vec.size()) && (w[vec[ind]] >= y[v])){
				mrg(vec[ind]);
				ind ++;
			}
			ll k = his.size();
			for(ll j : mrge[v]){
				mrg(j);
			}
			ans[v] = sz[get(x[v])];
			while(k < his.size()){
				roll_back();
			}
		}
		while(his.size())his.pop();
	}
	for(ll i = 1; i <= q; i ++){
		if(t[i] == 2)cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:95:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    while((ind < vec.size()) && (w[vec[ind]] >= y[v])){
      |           ~~~~^~~~~~~~~~~~
bridges.cpp:104:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::stack<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    while(k < his.size()){
      |          ~~^~~~~~~~~~~~

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