Submission #1044894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044894		Onur_Ilgaz	Bridges (APIO19_bridges)	C++17	0 / 100	202 ms	12084 KiB

bridges

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
vector <int> par, w;

int parent(int node) {
	if(par[node] == node) return node;
	return par[node] = parent(par[node]);
}

void dsu(int a, int b) {
	a = parent(a);
	b = parent(b);
	if(a == b) return;
	if(w[a] < w[b]) swap(a, b);
	// a ya byi ekle
	w[a] += w[b];
	par[b] = par[a];
}

void solve1(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > Queries) {
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		auto [a, b, c] = Edges[i];
		edges.push_back({a, b, c});
	}
	for(int i = 0; i < q; i++) {
		auto [type, a, b] = Queries[i];
		if(type == 1) {
			edges[a - 1][2] = b;
		}
		else {
			par.assign(n + 1, 0);
			w.assign(n + 1, 0);
			for(int i = 1; i <= n; i++) {
				par[i] = i;
				w[i] = 1;
			}
			for(auto [from, to, we]:edges) {
				// cout << from << " " << to << " " << we << "\n";
				if(we >= b) {
					// cout << from << " " << to << "\n";
					dsu(from, to);
				}
			}
			cout << w[parent(a)] << "\n";
		}
	}
}

void solve2(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > Queries) {
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		auto [a, b, c] = Edges[i];
		edges.push_back({c, a, b});
	}
	vector <array<int, 3> > queries;
	for(int i = 0; i < q; i++) {
		auto [type, a, b] = Queries[i];
		queries.push_back({b, a, i});
	}
	{
		sort(queries.begin(), queries.end());
		sort(edges.begin(), edges.end());
		reverse(queries.begin(), queries.end());
		reverse(edges.begin(), edges.end());
	}
	par.resize(n + 1);
	w.resize(n + 1);
	for(int i = 1; i <= n; i++) par[i] = i, w[i] = 1;

	vector <int> ans(q);
	int it = 0;
	for(auto [we, from, ind]:queries) {
		while(it < edges.size() and edges[it][0] >= we) {
			dsu(edges[it][1], edges[it][2]);
			it++;
		}
		ans[ind] = w[parent(from)];
	}
	for(int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}	
}

struct segtree {
	int n;
	vector <int> t;
	void init(int size) {
		n = size;
		t.resize(n * 4, inf);
	}
	void update(int v, int l, int r, int ind, int val) {
		if(l == r) {
			t[v] = val;
			return;
		}
		int m = (l + r) / 2;
		if(ind <= m) {
			update(v * 2, l, m, ind, val);
		}
		else {
			update(v * 2 + 1, m + 1, r, ind, val);
		}
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
	int query(int v, int l, int r, int ql, int qr) {
		if(l >= ql and r <= qr) {
			return t[v];
		}
		int m = (l + r) / 2;
		int ret = inf;
		if(ql <= m) {
			ret = min(ret, query(v * 2, l, m, ql, qr));
		}
		if(qr > m) {
			ret = min(ret, query(v * 2 + 1, m + 1, r, ql, qr));
		}
		return ret;
	}
};

void solve3(int n, int m, int q, vector <array<int, 3> > Edges, vector<array<int, 3> > queries) {
	segtree t;
	t.init(n);
	for(auto [a, b, w]:Edges) {
		t.update(1, 1, n, a, w);
	}
	for(auto [type, i, b]:queries) {
		if(type == 1) {
			t.update(1, 1, n, Edges[i - 1][0], b);
		}
		else {
			int ans = 0;
			// for right
			int l = 0, r = n - i + 1;
			while(r - l > 1) {
				int size = (l + r) / 2;
				if(t.query(1, 1, n, i, i + size - 1) < b) {
					r = size;
				}
				else {
					l = size;
				}
			}
			// cout << l << " " << r << "\n";
			ans += l;
			// for left
			l = 0, r = i - 1 + 1;
			while(r - l > 1) {
				int size = (l + r) / 2;
				if(t.query(1, 1, n, i, i - size + 1) < b) {
					r = size;
				}
				else {
					l = size;
				}
			}
			// cout << l << " " << r << "\n";
			ans += l;
			cout << ans + 1 << "\n";
		}
	}
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({a, b, c});
	}
	int q;
	cin >> q;
	vector <array<int, 3> > queries;
	bool yes1 = 0;
	for(int i = 0; i < q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		if(type == 1) yes1 = true;
		queries.push_back({type, a, b});
	}
	// if(!yes1) {
	// 	solve2(n, m, q, edges, queries);
	// }
	// else if(n <= 1000 and m <= 1000 and q <= 10000) {
	// 	solve1(n, m, q, edges, queries);
	// }
	// else {
	solve3(n, m, q, edges, queries);
	// }
}

Compilation message (stderr)

bridges.cpp: In function 'void solve2(long long int, long long int, long long int, std::vector<std::array<long long int, 3> >, std::vector<std::array<long long int, 3> >)':
bridges.cpp:77:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   while(it < edges.size() and edges[it][0] >= we) {
      |         ~~~^~~~~~~~~~~~~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:181:7: warning: variable 'yes1' set but not used [-Wunused-but-set-variable]
  181 |  bool yes1 = 0;
      |       ^~~~

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