Submission #319809

#	Time	Username	Problem	Language	Result	Execution time	Memory
319809		TeaTime	Bridges (APIO19_bridges)	C++17	13 / 100	3103 ms	127488 KiB

bridges

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
#include <unordered_map>
#include <bitset>

using namespace std;

typedef int ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 50002, INF = 1e9 + 100, SQ = 300;

ll n, m;
vector<pair<int, int>> edges, e;
vector<tuple<int, int, int>> edges2;
vector<tuple<int, int, int>> qs;

bool u[SZ];

vector<ll> wts;
vector<int> shit;

vector<int> upd;

int dsu[SZ][SQ + 5], s[SZ][SQ + 5];

int find(int v, int i) {
	if (dsu[v][i] == v) return v;
	else return dsu[v][i] = find(dsu[v][i], i);
}

void uni(int v, int u, int i) {
	u = find(u, i);
	v = find(v, i);

	if (u != v) {
		if (s[v] < s[u]) {
			swap(u, v);
		}

		dsu[u][i] = v;
		s[v][i] += s[u][i];
	}
}

void build(int i) {
	bool fl = 0;
	wts.clear();
	edges2.clear();
	upd.clear();
	for (int i = 0; i < m; i++) u[i] = 0;

	for (int j = i; j < min(ll(qs.size()), i + SQ); j++) {
		if (get<0>(qs[j]) == 2) {
			fl = 1;
			wts.push_back(get<2>(qs[j]));
		}
		if (get<0>(qs[j]) == 1) {
			int u2 = get<1>(qs[j]), v = get<2>(qs[j]);
			u[u2] = 1;
			upd.push_back(u2);
		}
	}
	
	if (!fl) return;

	for (int i = 0; i < m; i++) {
		if (u[i]) continue;
		pair<ll, ll> c = edges[i];
		edges2.push_back({ shit[i], c.first, c.second });
	}

	sort(edges2.rbegin(), edges2.rend());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < wts.size(); j++) {
			dsu[i][j] = i;
			s[i][j] = 1;
		}
	}

	sort(wts.rbegin(), wts.rend());

	ll j2 = 0;

	for (int i = 0; i < wts.size(); i++) {
		while (j2 < edges2.size() && get<0>(edges2[j2]) >= wts[i]) {
			uni(get<1>(edges2[j2]), get<2>(edges2[j2]), i);
			j2++;
		}

		for (int t = 0; t < n; t++) {
			dsu[t][i + 1] = dsu[t][i];
			s[t][i + 1] = s[t][i];
		}
	}
}

vector<vector<ll>> gr;
bool used[SZ];

int dfs(int v, int i) {
	used[v] = 1;

	int ss = 0;
	for (auto to : gr[v]) {
		if (!used[to]) ss += dfs(to, i);
	}

	return ss + s[v][i];
}

int main()
{
	fastInp;

	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		u--; v--;
		shit.push_back(c);
		e.push_back({ u, v });
		edges.push_back({ u, v });
		if (u > v) swap(u, v);
	}

	ll q;
	cin >> q;

	for (int i = 0; i < q; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		b--;
		qs.push_back({ a, b, c });
	}

	gr.resize(n);
	for (int i = 0; i < q; i++) {
		if (i % SQ == 0) {
			build(i);
		}

		if (get<0>(qs[i]) == 1) {
			int c, j;
			j = get<1>(qs[i]);
			c = get<2>(qs[i]);
			ll u = e[j].first, v = e[j].second;
			if (u > v) swap(u, v);
			shit[j] = c;
		}
		else {
			int v, w;
			v = get<1>(qs[i]);
			w = get<2>(qs[i]);

			int i2 = 0;
			for (i2 = 0; i2 < wts.size(); i2++) {
				if (wts[i2] == w) break;
			}

			for (auto c : upd) {
				int u = e[c].first, v = e[c].second;

				if (u > v) swap(u, v);
				if (shit[c] >= w) {
					u = find(u, i2);
					v = find(v, i2);
					gr[u].push_back(v);
					gr[v].push_back(u);
				}
			}

			cout << dfs(find(v, i2), i2) << "\n";

			used[find(v, i2)] = 0;

			for (auto c : upd) {
				int u = e[c].first, v = e[c].second;

				if (u > v) swap(u, v);
				if (shit[c] >= w) {
					u = find(u, i2);
					v = find(v, i2);
					gr[u].pop_back();
					gr[v].pop_back();
					used[u] = 0;
					used[v] = 0;
				}
			}
		}
	}

	return 0;
}

/*
5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1

3
1 1 1
2 2 2
3 3 3
*/

Compilation message (stderr)

bridges.cpp: In function 'void build(int)':
bridges.cpp:70:28: warning: unused variable 'v' [-Wunused-variable]
   70 |    int u2 = get<1>(qs[j]), v = get<2>(qs[j]);
      |                            ^
bridges.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int j = 0; j < wts.size(); j++) {
      |                   ~~^~~~~~~~~~~~
bridges.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < wts.size(); i++) {
      |                  ~~^~~~~~~~~~~~
bridges.cpp:98:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   while (j2 < edges2.size() && get<0>(edges2[j2]) >= wts[i]) {
      |          ~~~^~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:170:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |    for (i2 = 0; i2 < wts.size(); i2++) {
      |                 ~~~^~~~~~~~~~~~

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