Submission #494667

#	Time	Username	Problem	Language	Result	Execution time	Memory
494667		jjang36524	Bridges (APIO19_bridges)	C++14	100 / 100	2830 ms	13304 KiB

bridges

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define B 1000
struct dsu {
	ll p[2][MAX], num[2][MAX];
	ll chk[MAX],chkc;
	ll qnum = 0;
	void init(ll N) {
		ll i;
		chkc = 0;
		for (i = 1; i <= N; i++) p[0][i] = i, num[0][i] = 1, p[1][i] = 0, num[1][i] = 0;
	}
	inline ll find(ll v) 
	{
		while (1)
		{
			ll pp;
			if (!p[qnum][v]) pp = p[0][v];
			else pp = p[qnum][v];
			if (pp == v) return v;
			else {
				v = pp;
			}
		}
		
	}
	inline ll get(ll v)
	{
		if (!num[qnum][v]) return num[0][v];
		else return num[qnum][v];
	}
	void uni(ll a, ll b)
	{
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (get(b) < get(a)) swap(a, b);
		ll x = get(b) + get(a);
		p[qnum][a] = b;
		num[qnum][b] = x;
		if (qnum == 1)
		{
			chk[chkc++] = b;
			chk[chkc++] = a;
		}
	}
	void rb() 
	{
		for (int i=0;i<chkc;i++) 
		{ 
			num[1][chk[i]] = p[1][chk[i]] = 0; 
		}
		chkc = 0;
		qnum = 0;
	}
	void mark() {
		qnum++;
	}
}d;
struct query {
	ll t;
	ll b, r, s, w;
	ll ind;
	query(ll t, ll x, ll y, ll ind) :ind(ind) {
		query::t = t;
		if (t == 1) b = x, r = y;
		else s = x, w = y;
	}
	query() {}
};
pll edge[MAX];
ll val[MAX];
vector<query> qv[2000];
query qarr[MAX];
ll ans[MAX];
ll chk[MAX];
ll nchk[MAX];
bool cmp(query& a, query& b) {
	return a.w > b.w;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, M;
	cin >> N >> M;
	ll i;
	for (i = 1; i <= M; i++) {
		ll a, b;
		cin >> a >> b >> val[i];
		edge[i] = { a, b };
	}
	ll Q;
	cin >> Q;
	for (i = 1; i <= Q; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		qarr[i] = query(a, b, c, i);
		qv[(i - 1) / B].push_back(qarr[i]);
	}
	ll st, en;
	vector<pll> est;
	for (i = 1; i <= M; i++) est.push_back({ -val[i], i });
	for (i = 0; ; i++) {
		st = 1 + i * B;
		en = (1 + i) * B;
		en = min(en, Q);
		if (st > en) break;
		ll j;
		for (j = st; j <= en; j++) if (qarr[j].t == 1) chk[qarr[j].b] = 1;
		vector<query> qq;
		for (auto q : qv[i]) 
			if (q.t == 2) qq.push_back(q);
		if (qq.size()) sort(qq.begin(), qq.end(), cmp);
		vector<pll>::iterator it;
		sort(est.begin(), est.end());
		it = est.begin();
		int vv[1000];
		d.init(N);
		for (ll j = 0; j < qq.size(); j++)
		{
			for (; it != est.end(); it++) {
				if (chk[it->second]) continue;
				if (qq[j].w > -it->first) break;
				else d.uni(edge[it->second].first, edge[it->second].second);
			}
			if (it != est.begin()) it--;
			//dsu c = d;
			d.mark();
			ll cnt = 0;

			int vc = 0;
			int p = qq[j].ind;
			int w = qq[j].w;
			for (ll k = p; k >= st; k--) {
				if (qarr[k].t == 1) {
					if (qarr[k].r >= w && !nchk[qarr[k].b]) {
						d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second);
					}
					nchk[qarr[k].b] = 1;
					vv[vc++] = qarr[k].b;
				}
			}
			for (ll k = en; k > p; k--) {
				if (qarr[k].t == 1) {
					if (!nchk[qarr[k].b] && val[qarr[k].b] >= w) {
						d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second);
						nchk[qarr[k].b] = 1;
						vv[vc++] = qarr[k].b;
					}
				}
			}
			for (ll k = 0; k < vc; k++)
				nchk[vv[k]] = 0;
			ans[qq[j].ind] = d.get(d.find(qq[j].s));
			d.rb();
			//d = c;
		}
		est.clear();
		for (j = st; j <= en; j++) {
			if (qarr[j].t == 1) {
				chk[qarr[j].b] = 0;
				val[qarr[j].b] = qarr[j].r;
			}
		}
		for (j = 1; j <= M; j++)
		{
			est.push_back({ -val[j], j });
		}
	}
	for (i = 1; i <= Q; i++) if (qarr[i].t == 2) cout << ans[i] << ln;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:134:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for (ll j = 0; j < qq.size(); j++)
      |                  ~~^~~~~~~~~~~
bridges.cpp:144:7: warning: unused variable 'cnt' [-Wunused-variable]
  144 |    ll cnt = 0;
      |       ^~~

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