Submission #572454

#	Time	Username	Problem	Language	Result	Execution time	Memory
572454		CpDark	Bridges (APIO19_bridges)	C++14	16 / 100	411 ms	14176 KiB

bridges

#include <bits/stdc++.h>
#define fastInput ios::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pii;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;


struct segmentTree {
	vi st;
	int size;

	void init(int n) {
		for (size = 1; size < n; size *= 2) {}
		st.resize(2 * size);
	}

	void update(int index, int val) {
		index += size;
		st[index] = val;
		for (index /= 2; index; index /= 2) {
			st[index] = min(st[index * 2], st[index * 2 + 1]);
		}
	}

	int query(int l, int r) {
		int ans = INT_MAX;
		for (l += size, r += size; l <= r; l /= 2, r /= 2) {
			if (l % 2) {
				ans = min(ans, st[l]);
				l++;
			}
			if (r % 2 == 0) {
				ans = min(ans, st[r]);
				r--;
			}
		}
		return ans;
	}

};

vector<vp> graph;
vll weight;

vb visited;
segmentTree st;

int lastTrue(int s,int k, int lo, int hi) {
	lo--;
	while (lo < hi) {
		int mid = lo + (hi - lo + 1) / 2;
		bool curr = k <= st.query(s, mid);
		if (curr) {
			lo = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return lo;
}


int firstTrue(int s, int k, int lo, int hi) {
	hi++;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		bool curr = k <= st.query(mid, s);

		if (curr) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
	}
	return lo;
}


inline int findAmount(int root, int k, int n) {
	int ans = 1;
	int left = lastTrue(root, k, root, n - 1);
	ans += left - root + 1;
	int right = firstTrue(root - 1, k, 1, root - 1);
	ans += root - 1 - right + 1;
	return ans;

}

void dfs(int v, int k) {
	visited[v] = true;
	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		ll w = weight[graph[v][i].second];
		if (k <= w && !visited[u]) {
			dfs(u, k);
		}
	}
}

int main() {
	fastInput;
	int n, m;
	cin >> n >> m;

	st.init(n);
	graph.resize(n + 1);
	weight.resize(m + 1);
	int a, b, d;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> d;
		graph[a].push_back({ b,i });
		graph[b].push_back({ a,i });
		weight[i] = d;
		st.update(i, d);
	}


	int q;
	cin >> q;
	int t;
	for (int i = 0; i < q; i++) {
		cin >> t;
		if (t == 1) {
			 int r;
			 cin >> b >> r;
			 weight[b] = r;
			 st.update(b, weight[b]);
		}
		else {
			int s, w;
			cin >> s >> w;
			int ans = findAmount(s, w, n);
			cout << ans << endl;
		}
	}


	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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