Submission #253544

#	Time	Username	Problem	Language	Result	Execution time	Memory
253544		DystoriaX	Bridges (APIO19_bridges)	C++14	100 / 100	2481 ms	6520 KiB

bridges

#include <bits/stdc++.h>
 
#define fi first
#define se second
 
using namespace std;
 
typedef pair<int, int> pii;
 
struct Node{
	int u, sz_u, v, sz_v;
};
 
struct Query{
	int type, a, b, idx;
};
 
const int sq = 900;
 
int n, m, q;
 
int p[50010], sz[50010];
Node st[100010];
int cz;
 
pii edges[100010];
vector<int> eg;
 
int w[100010];
 
Query qry[100010];
int ans[100010];
 
void init(){
	iota(p, p + n + 1, 0);
	fill(sz, sz + n + 1, 1);
	cz = 0;
}
 
int findR(int x){
	return p[x] == x ? x : findR(p[x]);
}
 
void join(int a, int b){
	a = findR(a), b = findR(b);
 
	st[cz++] = Node({a, sz[a], b, sz[b]});
 
	if(a == b) return;
 
	if(sz[a] > sz[b]) swap(a, b);
 
	p[a] = b;
	sz[b] += sz[a];
}
 
void rollback(){
	Node x = st[--cz];
 
	p[x.u] = x.u;
	p[x.v] = x.v;
 
	sz[x.u] = x.sz_u;
	sz[x.v] = x.sz_v;
}
 
bool cmp(Query a, Query b){
	return a.b > b.b;
}
 
bool egCmp(int a, int b){
	return w[a] > w[b];
}
 
bitset<100010> dead, vis;
 
void Process(int l, int r){
	vector<Query> updates, queries;
 
	for(int i = l; i <= r; i++){
		if(qry[i].type == 1) updates.emplace_back(qry[i]);
		else queries.emplace_back(qry[i]);
	}
 
	sort(queries.begin(), queries.end(), cmp);
	sort(eg.begin(), eg.end(), egCmp);
 
	//We process from rightmost to leftmost, getting the most updated weight of edge
	reverse(updates.begin(), updates.end());
 
	for(auto &k : updates) dead[k.a] = true;
 
	int id = 0;
 
	init();
	for(auto &k : queries){
		while(id < m && w[eg[id]] >= k.b){
			if(!dead[eg[id]]) join(edges[eg[id]].fi, edges[eg[id]].se);
			id++;
		}
 
		int cur_size = cz;
 
		for(auto &ed : updates){
			if(ed.idx < k.idx){
				if(vis[ed.a]) continue;
 
				vis[ed.a] = true;
 
				if(ed.b >= k.b) join(edges[ed.a].fi, edges[ed.a].se);
			}
		}
 
		for(auto &ed : updates){
			if(ed.idx < k.idx) break;
			if(!vis[ed.a] && w[ed.a] >= k.b) join(edges[ed.a].fi, edges[ed.a].se);
		}
 
		ans[k.idx] = sz[findR(k.a)];
 
		for(auto &ed : updates){
			vis[ed.a] = false;
		}
 
		while(cz > cur_size) rollback();
	}
 
	for(auto &k : updates){
		if(!dead[k.a]) continue;
		dead[k.a] = false;
		w[k.a] = k.b;
	}
}
 
int main(){
	// cerr << sq << "\n";
	scanf("%d%d", &n, &m);
 
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]);
	}
 
	scanf("%d", &q);
 
	for(int i = 1; i <= q; i++){
		scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b);
		qry[i].idx = i;
	}
 
	memset(ans, -1, sizeof(ans));
 
	eg.resize(m);
	iota(eg.begin(), eg.end(), 1);
	for(int i = 0; i * sq + 1 <= q; i++){
		Process(i * sq + 1, min(q, (i + 1) * sq));
	}
 
	for(int i = 1; i <= q; i++){
		if(ans[i] == -1) continue;
		printf("%d\n", ans[i]);
	}
	
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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