Submission #572477

#	Time	Username	Problem	Language	Result	Execution time	Memory
572477		CpDark	Bridges (APIO19_bridges)	C++14	0 / 100	3060 ms	524288 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<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;

const int inf = 1e9 + 7;

struct CentroidDecomposition {
	vvp graph;
	vi subSize;
	int n;
	int centroid = -1;

	void init(int N, vvp& g) {
		n = N;
		graph = g;
		subSize.resize(n + 1);
	}

	void dfs(int v, int p) {
		subSize[v] = 1;
		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			if (u != p) {
				dfs(u, v);
				subSize[v] += subSize[u];
			}
		}
	}

	int findCentroid(int v, int p) {
		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			if (u != p && subSize[u] > n / 2) {
				return findCentroid(u, v);
			}
		}
		return v;
	}

	int getCentroid() {
		if (centroid == -1) {
			dfs(1, 1);
			centroid = findCentroid(1, 1);
		}
		return centroid;
	}
};

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;

}

inline void mergeSets(set<pii> &a, set<pii> &b, int w) {
	auto it = b.begin();
	for (int i = 0; i < b.size(); i++) {
		pii curr = *it;
		if (curr.first > w)curr.first = w;
		auto f = a.lower_bound({ curr.first,-1 });
		if (f != a.end() && ((pii)*f).first == curr.first) {
			pii val = { curr.first, curr.second + ((pii)*f).second };
			a.erase(f);
			a.insert(val);
		}
		else {
			a.insert(curr);
		}
		it++;
	}
}
vp bridges;
vp par;
vi depth;
vector<set<pii>> hold;
void dfs(int v, int p, int d, int wp) {
	depth[v] = d;
	par[v] = { p,wp };
	hold[v].insert({ inf,1 });
	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		ll w = weight[graph[v][i].second];
		if (u != p) {
			dfs(u, v, d + 1, graph[v][i].second);
			mergeSets(hold[v], hold[u], w);
		}
	}
}



inline void updatehold(int index) {
	pii edge = bridges[index];
	int upper = edge.first;
	int lower = edge.second;
	if (depth[upper] > depth[lower]) swap(upper, lower);

	int v = lower;
	while (par[v].first != v) {
		v = par[v].first;
		hold[v].clear();
		hold[v].insert({ inf,1 });
		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			ll w = weight[graph[v][i].second];
			if (u != par[v].first) {
				mergeSets(hold[v], hold[u], w);
			}
		}
	}
}


inline int getsub(int v, int w) {
	int ans = 0;
	auto it = hold[v].end();
	it--;

	for (int i = 0; i < hold[v].size(); i++) {
		pii curr = *it;
		if (w > curr.first) return ans;
		ans += curr.second;
		it--;
	}
	return ans;
}

inline int maxReach(int v, int w) {
	if (v == par[v].first)return v;
	if (w <= weight[par[v].second]) {
		return maxReach(par[v].first, w);
	}
	return v;
}


inline int queryCount(int s, int w) {
	int p = maxReach(s, w);
	int pc = getsub(p, w);
	int sc = getsub(s, w);
	if (p == par[s].first) sc = 1;

	int ans = pc - sc + 1;
	return ans;
}

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

	//st.init(n);
	graph.resize(n + 1);
	weight.resize(m + 1);
	bridges.resize(m + 1);
	par.resize(n + 1);
	depth.resize(n + 1);
	hold.resize(n + 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 });
		bridges[i] = { a,b };
		weight[i] = d;
		//st.update(i, d);
	}
	CentroidDecomposition cd;
	cd.init(n + 1, graph);
	int root = cd.getCentroid();
	dfs(root, root, 1, -1);

	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;
			 updatehold(b);
		}
		else {
			int s, w;
			cin >> s >> w;
			int ans = queryCount(s, w);
			cout << ans << endl;
		}
	}


	return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void CentroidDecomposition::dfs(int, int)':
bridges.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In member function 'int CentroidDecomposition::findCentroid(int, int)':
bridges.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void mergeSets(std::set<std::pair<int, int> >&, std::set<std::pair<int, int> >&, int)':
bridges.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
bridges.cpp: In function 'void dfs(int, int, int, int)':
bridges.cpp:168:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void updatehold(int)':
bridges.cpp:191:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int getsub(int, int)':
bridges.cpp:207:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |  for (int i = 0; i < hold[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

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