Submission #739142

#	Time	Username	Problem	Language	Result	Execution time	Memory
739142		josanneo22	Bridges (APIO19_bridges)	C++17	100 / 100	1935 ms	31800 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
 
const int B = 1000;
int n, m, q;
 
stack<int> stck;
int sz[100001], cmp[100001];
 
void reset() {
	iota(cmp + 1, cmp + 1 + n, 1);
	fill(sz + 1, sz + n + 1, 1);
}
 
inline int find(int a) {
	while (cmp[a] != a) a = cmp[a];
	return a;
}
 
void onion(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	stck.push(a);
	sz[b] += sz[a];
	cmp[a] = cmp[b];
}
 
void rollback(int x) {
	while (stck.size() > x) {
		int k = stck.top();
		stck.pop();
		sz[cmp[k]] -= sz[k];
		cmp[k] = k;
	}
}
 
int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
bool changed[100001];
vector<int> to_join[B];
int ans[100001];
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int s=0;
	char ch=getchar(),last;
	while(ch<'0'||ch>'9') last=ch,ch=getchar();
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return last=='-'?-s:s;
}
int num[100];
inline void rt(int pp)
{
	if(pp<0) putchar('-'),pp=-pp;;
	int len=0;
	do num[len++]=pp%10;while(pp/=10);
	while(len--) putchar(num[len]+'0');
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    n=rd(); m=rd();
	FOR(i, 1, m + 1) {u[i]=rd();v[i]=rd();w[i]=rd();}
	q=rd();
	FOR(i, 1, q + 1) {t[i]=rd();x[i]=rd();y[i]=rd();}
 
	for (int l = 1; l <= q; l += B) {
		int r = min(q + 1, l + B);
		reset();
		fill(changed + 1, changed + m + 1, false);
 
		vector<int> ask, upd, unchanged;
		FOR(i, l, r) {
			if (t[i] == 1) {
				changed[x[i]] = true;
				upd.push_back(i);
			} else ask.push_back(i);
		}
		FOR(i, 1, m + 1) if (!changed[i]) unchanged.push_back(i);
 
		FOR(i, l, r) {
			if (t[i] == 1) w[x[i]] = y[i];
			else {
				to_join[i - l].clear();
				for (int j : upd)
					if (w[x[j]] >= y[i]) to_join[i - l].push_back(x[j]);
			}
		}
 
		sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
		sort(unchanged.begin(), unchanged.end(),
		     [&](int a, int b) { return w[a] > w[b]; });
 
		int ptr = 0;
		for (int i : ask) {
			while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
				onion(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = stck.size();
			for (int j : to_join[i - l]) onion(u[j], v[j]);
			ans[i] = sz[find(x[i])];
			rollback(prev_size);
		}
	}
 
	FOR(i, 1, q + 1) if (t[i] == 2){
        rt(ans[i]);
        printf("\n");
    }
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |  while (stck.size() > x) {
      |         ~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
      |           ~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int rd()':
bridges.cpp:58:18: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  return last=='-'?-s:s;
      |         ~~~~~~~~~^~~~~

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