Submission #253538

#	Time	Username	Problem	Language	Result	Execution time	Memory
253538		DystoriaX	Bridges (APIO19_bridges)	C++14	100 / 100	2714 ms	7064 KiB

bridges

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;

struct Query{
	int type, a, b, idx;
};

const int sq = 750;

int n, m, q;

int p[50010], sz[50010];

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);
}

int findR(int x){
	return p[x] == x ? x : p[x] = findR(p[x]);
}

void join(int a, int b){
	a = findR(a), b = findR(b);

	if(a == b) return;

	if(sz[a] > sz[b]) swap(a, b);

	p[a] = b;
	sz[b] += sz[a];
}

bool cmp(Query a, Query b){
	return a.b > b.b;
}

bool egCmp(int a, int b){
	return w[a] > w[b];
}

vector<int> adj[50010];
bitset<100010> dead, vis, visited;
vector<int> added;

void add_edge(int idx){
	int u, v;
	u = findR(edges[idx].fi), v = findR(edges[idx].se);

	if(u == v) return;

	added.emplace_back(idx);
	adj[u].emplace_back(v);
	adj[v].emplace_back(u);
}

void remove(){
	for(auto &k : added){
		int u = findR(edges[k].fi), v = findR(edges[k].se);

		adj[u].clear();
		adj[v].clear();
		visited[u] = visited[v] = false;
	}

	added.clear();
}

int dfs(int u){
	visited[u] = true;
	int ret = sz[u];

	for(auto &v : adj[u]){
		if(!visited[v]) ret += dfs(v);
	}

	return ret;
}

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++;
		}

		for(auto &ed : updates){
			if(ed.idx < k.idx){
				if(vis[ed.a]) continue;

				vis[ed.a] = true;

				if(ed.b >= k.b) add_edge(ed.a);
			}
		}

		for(auto &ed : updates){
			if(ed.idx < k.idx) break;
			if(!vis[ed.a] && w[ed.a] >= k.b) add_edge(ed.a);
		}

		ans[k.idx] = dfs(findR(k.a));
		visited[findR(k.a)] = false;

		for(auto &ed : updates){
			vis[ed.a] = false;
		}

		remove();
	}

	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:153: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:156: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:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:162: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