Submission #209537

#	Time	Username	Problem	Language	Result	Execution time	Memory
209537		mieszko11b	Bridges (APIO19_bridges)	C++14	100 / 100	1979 ms	16756 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

const int SQRT = 600;

int n, m;
int a[100007], b[100007], c[100007];
int q;
int t[100007], d[100007], e[100007], ans[100007];
bool changed[100007];
int lastw[100007];
int maxv;
vector<int> not_changed[200007];
vector<int> G[50007];

void readint(int &x) {
	x = 0;
	char c;
	do
		c = getchar_unlocked();
	while(c < '0' || c > '9');
	
	do {
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	} while(c >= '0' && c <= '9');
}

int p[50007], ran[50007];
bool vis[50007];

int cnt;
vector<int> aff;

void init_DSU() {
	for(int i = 1 ; i <= n ; i++) {
		p[i] = i;
		ran[i] = 1;
	}
}

int Find(int i) {
	if(p[i] == i)
		return i;
	return p[i] = Find(p[i]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	
	if(a == b)
		return ;
		
	if(ran[a] < ran[b]) {
		p[a] = b;
		ran[b] += ran[a];
	} else {
		p[b] = a;
		ran[a] += ran[b];
	}
}

void dfs(int w) {
	if(vis[w])
		return ;
	vis[w] = 1;
	aff.push_back(w);
	cnt += ran[w];
	for(int u : G[w])
		dfs(u);
}

int count(vector<ii> &E, int w) {
	for(ii e : E) {
		G[e.X].push_back(e.Y);
		G[e.Y].push_back(e.X);
	}
	cnt = 0;
	aff.reserve(100);
	dfs(Find(w));
	for(int x : aff)
		vis[x] = 0;
	aff.clear();
	for(ii e : E) {
		G[e.X].clear();
		G[e.Y].clear();
	}
	return cnt;
}


void process_queries(int x, int y) {
	vector<ii> Q;
	vector<int> chacha;
	chacha.reserve(y - x + 1);
	Q.reserve(y - x + 1);

	for(int i = x ; i <= y ; i++) {
		if(t[i] == 1)
			changed[d[i]] = 1;
		else
			Q.emplace_back(e[i], i);
	}
	for(int j = 0 ; j < maxv ; j++)
		not_changed[j].clear();
	for(int i = 1 ; i <= m ; i++) {
		if(!changed[i])
			not_changed[c[i]].push_back(i);
		else
			chacha.push_back(i);
	}
	sort(Q.begin(), Q.end(), greater<ii>());
	
	init_DSU();
	
	int v = maxv;
	for(int j = 0 ; j < Q.size() ; j++) {
		int q = Q[j].Y;
		
		for(int i = e[q] ; i < v ; i++)
			for(int e : not_changed[i])
				Union(a[e], b[e]);
		v = e[q];
				
		for(int e : chacha)
			lastw[e] = c[e];
		for(int k = x ; k < q ; k++)
			if(t[k] == 1)
				lastw[d[k]] = e[k];
		vector<ii> E;
		E.reserve(y - x + 1);
		for(int e : chacha)
			if(lastw[e] >= ::e[q])
				E.push_back({Find(a[e]), Find(b[e])});
		ans[q] = count(E, d[q]);
	}

	for(int k = x ; k <= y ; k++)
		if(t[k] == 1)
			c[d[k]] = e[k], changed[d[k]] = 0;
}

vector<int> hlp;
int renum(int x) {
	auto it = upper_bound(hlp.begin(), hlp.end(), x);
	return prev(it) - hlp.begin();
}	

int main() {
	//~ scanf("%d%d",&n, &m);
	readint(n);
	readint(m);
	
	for(int i = 1 ; i <= m ; i++) {
		//~ scanf("%d%d%d", &a[i], &b[i], &c[i]);
		readint(a[i]);
		readint(b[i]);
		readint(c[i]);
		//~ hlp.push_back(c[i]);
	}
	//~ scanf("%d", &q);
	readint(q);
	for(int i = 1 ; i <= q ; i++) {
		//~ scanf("%d%d%d", &t[i], &d[i], &e[i]);
		readint(t[i]);
		readint(d[i]);
		readint(e[i]);
		if(t[i] == 2)
			hlp.push_back(e[i]);
	}
	hlp.push_back(0);
	hlp.push_back(int(1e9) + 7);
		
	sort(hlp.begin(), hlp.end());
	hlp.resize(distance(hlp.begin(), unique(hlp.begin(), hlp.end())));
	maxv = hlp.size();
	for(int i = 1 ; i <= m ; i++)
		c[i] = renum(c[i]);
	//~ cout << endl;
	for(int i = 1 ; i <= q ; i++)
		e[i] = renum(e[i]);
	//~ cout << endl;
		
	for(int i = 1 ; i <= q ; i += SQRT)
		process_queries(i, min(i + SQRT - 1, q));
		
	for(int i = 1 ; i <= q ; i++)
		if(ans[i])
			printf("%d\n", ans[i]);
		
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void process_queries(int, int)':
bridges.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < Q.size() ; j++) {
                  ~~^~~~~~~~~~

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