Submission #403316

#	Time	Username	Problem	Language	Result	Execution time	Memory
403316		hoaphat1	Bridges (APIO19_bridges)	C++17	100 / 100	1372 ms	9152 KiB

bridges

#include<bits/stdc++.h>
 
using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifndef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

struct dsu {
	struct node {
		int* p;
		int val;
		int time;
	};
	vector<node> event = {{NULL, 0, -1}};
	vector<int> p;
	int n;
	dsu(int n) {
		resize(n);
	}
	dsu() {
	}
	void resize(int _n) {
		n = _n;
		p = vector<int> (n, -1);
	}
	int count = 0;
	int get(int x) {
		return p[x] < 0 ? x : get(p[x]);
	}
	bool unite(int x, int y, bool need = false) {
		x = get(x); y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			if (need) {
				event.push_back({&p[x], p[x], count});
				event.push_back({&p[y], p[y], count});
			}
			p[y] += p[x];
			p[x] = y;
			return true;
		}
		return false;
	}
	void recall() {
		while (event.back().time == count) {
			*event.back().p = event.back().val;
			event.pop_back();
		}
		--count;
	}
};

struct edge {
	int u;
	int v;
	int w;
};

int main() {
	#define qwer "test"
	if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _, n, m;
	//cin >> _;
	cin >> n >> m;
	vector<edge> edges;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		--u; --v;
		edges.push_back({u, v, w});
	}
	int q;
	cin >> q;
	vector<tuple<int, int, int>> Query;
	for (int i = 0; i < q; i++) {
		int t, u, w;
		cin >> t >> u >> w;
		--u;
		Query.emplace_back(t, u, w);
	}
	int sq = 2 * sqrt(q);
	vector<int> ans(q);
	vector<int> to(m, -1);
	/*
		x/4 * q + q/x * q
		q * (x/4 + q/x) >= sqrtq sqrt17
	*/
	vector<int> p(m);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j) {
		return edges[i].w > edges[j].w;
	});
	for (int l = 0; l < q; l += sq) {
		int r = min(q, l + sq);
		dsu d(n);
		vector<int> ask;
		vector<int> rem;
		vector<int> now;
		for (int i = l; i < r; i++) {
			if (get<0>(Query[i]) == 1) {
				if (to[get<1>(Query[i])] == -1) {
					rem.push_back(get<1>(Query[i]));
					to[rem.back()] = edges[rem.back()].w;
				}
				now.push_back(i);
			}
			else {
				ask.push_back(i);
			}
		}
		vector<int> id;
		for (int i = 0; i < m; i++) if (to[p[i]] == -1) id.push_back(p[i]);
		sort(ask.begin(), ask.end(), [&](int i, int j) {
			return get<2>(Query[i]) > get<2>(Query[j]);
		});
		int j = 0;
		for (auto& i : ask) {
			while (j < (int) id.size() && edges[id[j]].w >= get<2>(Query[i])) {
				d.unite(edges[id[j]].u, edges[id[j]].v);
				j++;
			}
			for (auto&x : now) {
				if (x > i) break;
				to[get<1>(Query[x])] = get<2>(Query[x]);
			}
			d.count++;
			for (auto&x : rem) {
				if (to[x] >= get<2>(Query[i])) {
					d.unite(edges[x].u, edges[x].v, 1);
				}
				to[x] = edges[x].w;
			}
			ans[i] = -d.p[d.get(get<1>(Query[i]))];
			d.recall();
		}
		for (auto&x : now) {
			edges[get<1>(Query[x])].w = get<2>(Query[x]);
		}
		sort(rem.begin(), rem.end(), [&](int i, int j) {
			return edges[i].w > edges[j].w;
		});
		merge(id.begin(), id.end(), rem.begin(), rem.end(), p.begin(), [&](int i, int j) {
			return edges[i].w > edges[j].w;
		});
		for (auto&x : rem) {
			to[x] = -1;
		}
	}
	for (int i = 0; i < q; i++) if (get<0>(Query[i]) == 2) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:149:6: warning: unused variable '_' [-Wunused-variable]
  149 |  int _, n, m;
      |      ^
bridges.cpp:146:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:146:67: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
      |                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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