Submission #253486

#	Time	Username	Problem	Language	Result	Execution time	Memory
253486		DystoriaX	Bridges (APIO19_bridges)	C++14	59 / 100	3067 ms	7612 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 = 400;

int n, m, q;

int p[50010], sz[50010];
stack<Node> st;

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);
	while(!st.empty()) st.pop();
}

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.push(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.top(); st.pop();

	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 = st.size();

		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((int) st.size() > 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:136: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:139: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:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:145: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: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27