Submission #156955

#	Time	Username	Problem	Language	Result	Execution time	Memory
156955		popovicirobert	Bridges (APIO19_bridges)	C++14	100 / 100	2849 ms	21292 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const int MAXN = 50000;
const int MAXM = (int) 1e5;
const int B = 1500;

struct DSU {
	vector <int> par, sz;
	int n;

	inline void init(int _n) {
		n = _n;
		par.resize(n + 1), sz.resize(n + 1, 1);
	}

	int root(int x) {
		if(par[x] == 0) return x;
		return par[x] = root(par[x]);
	}

	inline void join(int x, int y) {
		x = root(x), y = root(y);
		if(x != y) {
			par[x] = y;
			sz[y] += sz[x];
		}
	}
};

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

struct Data {
	int w, nod, pos;
	bool operator <(const Data &other) const {
		return w < other.w;
	}
};
   
int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, m, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	vector < vector < pair <int, int> > > g(n + 1);
	vector <int> weight(m + 1), x(m + 1), y(m + 1);

	for(i = 1; i <= m; i++) {
		cin >> x[i] >> y[i] >> weight[i];
		g[x[i]].push_back({y[i], i});
		g[y[i]].push_back({x[i], i});
	}

	cin >> q;
	vector <Query> qry(q);
	for(i = 0; i < q; i++) {
		cin >> qry[i].type >> qry[i].a >> qry[i].b;
	}

	DSU dsu; dsu.init(n);
	
	vector < vector < pair <int, int> > > G(n + 1);
	vector <int> sol(q + 1), curw(m + 1);
	vector <bool> vis(m + 1);
	vector <int> mark(n + 1);
	int now = 0;

	function <int(int, int)> dfs = [&](int nod, int w) {
		nod = dsu.root(nod);
		if(mark[nod] == now) return 0;
		int ans = dsu.sz[nod];
		mark[nod] = now;
		for(auto it : G[nod]) {
			if(curw[it.second] >= w) {
				ans += dfs(it.first, w);
			}
		}
		return ans;
	};	

	for(i = 0; i < q; i += B) {
		for(j = 1; j <= n; j++) {
			G[j].clear();
			dsu.par[j] = 0, dsu.sz[j] = 1;
		}
		fill(vis.begin(), vis.end(), 0);
		vector <Data> nodes;

		int lim = min(q, i + B);
		for(j = i; j < lim; j++) {
			if(qry[j].type == 1) {
				vis[qry[j].a] = 1;
			}
			else {
				nodes.push_back({qry[j].b, qry[j].a, j});
			}
		}

		vector < pair <int, int> > edges;
		for(j = 1; j <= m; j++) {
			curw[j] = weight[j];
			if(vis[j] == 0) {
				edges.push_back({weight[j], j});
			}
			else {
				G[x[j]].push_back({y[j], j});
				G[y[j]].push_back({x[j], j});
			}
		}

		sort(edges.begin(), edges.end());
		sort(nodes.rbegin(), nodes.rend());

		int pos = (int) edges.size() - 1;
		for(auto &it : nodes) {
			while(pos >= 0 && it.w <= edges[pos].first) {
				int id = edges[pos].second;
				int a = dsu.root(x[id]), b = dsu.root(y[id]);
				if(a != b) {
					if(G[a].size() > G[b].size()) {
						swap(a, b);
					}
					for(auto &it : G[a]) {
						G[b].push_back(it);
					}
					dsu.join(a, b);
				}
				pos--;
			}
			for(j = i; j < it.pos; j++) {
				if(qry[j].type == 1) {
					curw[qry[j].a] = qry[j].b;
				}
			}
			now++;
			sol[it.pos] = dfs(it.nod, it.w);
			for(j = i; j < it.pos; j++) {
				if(qry[j].type == 1) {
					curw[qry[j].a] = weight[qry[j].a];
				}
			}
		}
		
		for(j = i; j < lim; j++) {
			if(qry[j].type == 1) {
				weight[qry[j].a] = qry[j].b;
			}
		}
	}

	for(i = 0; i < q; i++) {
		if(qry[i].type == 2) {
			cout << sol[i] << "\n";
		}
	}
		
	return 0;
}

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