Submission #564344

#	Time	Username	Problem	Language	Result	Execution time	Memory
564344		ngpin04	Bridges (APIO19_bridges)	C++14	100 / 100	2541 ms	18940 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int K = 500;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> a[2 * N];

int val[2 * N];
int *where[2 * N];

int tmpw[N];
int ind[N];
int ans[N];
int par[N];
int fr[N];
int to[N];
int op[N];
int w[N];
int s[N];
int d[N];
int n,m,q,timer;

bool flag[N];

void rollback() {
	*where[timer] = val[timer];
	timer--;
}

void change(int &a, int b) {
	timer++;
	where[timer] = &a;
	val[timer] = a;
	a = b;
}

int getpar(int u) {
	return (par[u] < 0) ? u : (getpar(par[u]));
}

void join(int u, int v) {
	u = getpar(u);
	v = getpar(v);
	if (u == v)
		return;
	if (par[u] > par[v])
		swap(u, v);
	change(par[u], par[u] + par[v]);
	change(par[v], u);
}

void compress() {
	vector <int> val;
	for (int i = 1; i <= m; i++)
		val.push_back(w[i]);

	for (int i = 1; i <= q; i++)
		val.push_back(d[i]);
	sort(ALL(val));

	for (int i = 1; i <= m; i++)
		w[i] = lower_bound(ALL(val), w[i]) - val.begin() + 1;

	for (int i = 1; i <= q; i++)
		d[i] = lower_bound(ALL(val), d[i]) - val.begin() + 1;
}

void solve(int l, int r) {
	timer = 0;
	for (int i = 1; i <= n; i++)
		par[i] = -1;

	for (int i = 1; i <= m; i++)
		flag[i] = false;

	vector <int> ed;
	vector <int> qr;
	for (int i = l; i <= r; i++) {
		if (op[i] == 1) {
			ed.push_back(s[i]);
			flag[s[i]] = true;
		} else
			qr.push_back(i);
	}

	sort(ALL(qr), [](int i, int j) {
		return d[i] > d[j];
	});

	{
		for (int i = 1; i <= m; i++) 
			a[w[i]].push_back(i);

		int it = 0;
		for (int i = m + q; i >= 1; i--) {
			for (int j : a[i])
				ind[++it] = j;
			a[i].clear();
		}
	}

	int it = 1;
	for (int i : qr) {
		while (it <= m && w[ind[it]] >=	d[i]) {
			if (!flag[ind[it]])
				join(fr[ind[it]], to[ind[it]]);
			it++;
		}

		int cur = timer;
		for (int j = l; j <= i; j++) 
			if (op[j] == 1) 
				tmpw[s[j]] = d[j];
		
		for (int j : ed) {
			int val = (tmpw[j] == 0) ? w[j] : tmpw[j];
			if (val >= d[i])
				join(fr[j], to[j]);
		}

		ans[i] = -par[getpar(s[i])];

		for (int j : ed)
			tmpw[j] = 0;

		while (timer != cur)
			rollback();
	}	

	for (int i = l; i <= r; i++) 
		if (op[i] == 1)
			w[s[i]] = d[i];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> m;
	for (int i = 1; i <= m; i++) 
		cin >> fr[i] >> to[i] >> w[i];
	
	cin >> q;
	for (int i = 1; i <= q; i++)
		cin >> op[i] >> s[i] >> d[i];

	compress();

	for (int l = 1; l <= q; l++) {
		int r = min(q, l + K);

		solve(l, r);
		l = r;
	}

	for (int i = 1; i <= q; i++)
		if (op[i] == 2)
			cout << ans[i] << "\n";
	return 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