oj.uz

Submission #566069

# Submission time Handle Problem Language Result Execution time Memory
566069 2022-05-21T17:55:28 Z Bungmint Bridges (APIO19_bridges) C++17
100 / 100
 2937 ms 10280 KB 
// Copyright © 2022 Youngmin Park. All rights reserved.
#pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
	return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
	os << '{';
	string sep;
	for (const T &x : v)
		os << sep << x, sep = ", ";
	return os << '}';
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
	os << vector<T>(all(v));
	return os;
}
template <typename T, typename S, typename C>
ostream &operator<<(ostream &os, priority_queue<T, S, C> pq) {
	vector<T> v;
	while (sz(pq)) {
		v.pb(pq.top());
		pq.pop();
	}
	os << v;
	return os;
}
void dbg_out()
{
	cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
	cerr << ' ' << H;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "\033[1;35m(" << #__VA_ARGS__ << "):\033[33m", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda
{
	template <typename Fun>
	struct y_combinator_result
	{
		Fun fun_;
		template <typename T>
		explicit y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		decltype(auto) operator()(Args &&...args)
		{
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun)
	{
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

inline namespace Range {
	class ForwardRange {
		int src, dst;

	  public:
	  	explicit constexpr ForwardRange(const int l, const int r) : src(l), dst(r) {}
		explicit constexpr ForwardRange(const int n) : src(0), dst(n) {}
		constexpr ForwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src < dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return src++; }
	};
	class BackwardRange {
		int src, dst;

	  public:
	  	explicit constexpr BackwardRange(const int l, const int r) : src(r), dst(l) {}
		explicit constexpr BackwardRange(const int n) : src(n), dst(0) {}
		constexpr BackwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src > dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return --src; }
	};
	using rep = ForwardRange;
	using per = BackwardRange;
};

// From the USACO tutorial lol
template <int N>
struct DSU {
	int e[N];
	vector<int> mem;
	vector<pair<pii, pii>> ev;
	DSU() { memset(e, -1, sizeof(e)); }

	// get representive component (uses path compression)
	// To use rollback, disable path compression
	inline int get(int x) { return e[x] < 0 ? x : get(e[x]); }
	
	bool same_set(int a, int b) { return get(a) == get(b); }
	
	int size(int x) { return -e[get(x)]; }
	
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		ev.pb({{x, e[x]}, {y, e[y]}});
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;
		return true;
	}
	
	void snapshot(){
		mem.pb(sz(ev));
	}
	
	void rollback(){
		if (mem.empty()) return;
		int SZ = mem.back();
		mem.pop_back();
		while(sz(ev) != SZ){
			pair<pii, pii> p = ev.back();
			e[p.fi.fi] = p.fi.se;
			e[p.se.fi] = p.se.se;
			ev.pop_back();
		}
	}

	void clear() {
		memset(e, -1, sizeof(e));
		mem.clear();
		ev.clear();
	}
};



constexpr int SQ = 500, NN = 1e5 + 100;
bitset<NN> used;
int ans[NN];
vi toJoin[SQ + 100];
int u[NN], v[NN], w[NN];
int ty[NN], id[NN], ww[NN];
DSU<NN> dsu{};

void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i : rep(m)) {
		cin >> u[i] >> v[i] >> w[i];
		u[i]--, v[i]--;
	}
	int q;
	cin >> q;
	for (int i : rep(q)) {
		cin >> ty[i] >> id[i] >> ww[i];
		id[i]--;
	}
	for (int L = 0; L < q; L += SQ) {
		vi upd, calc, unchanged;
		dsu.clear();
		int R = min(L + SQ - 1, q - 1);
		for (int i : rep(L, R + 1)) {
			if (ty[i] == 1) upd.pb(i), used[id[i]] = 1;
			else calc.pb(i);
		}
		for (int j : rep(m)) {
			if (!used[j]) unchanged.pb(j);
		}
		for (int j : rep(L, R + 1)) {
			if (ty[j] == 1) {
				w[id[j]] = ww[j];
			}else{
				toJoin[j - L].clear();
				for (auto &e : upd) {
					if (w[id[e]] >= ww[j]) toJoin[j - L].pb(id[e]);
				}
			}
		}
		sort(all(calc), [&](auto x, auto y) {
			return ww[x] > ww[y];
		});
		sort(all(unchanged), [&](auto x, auto y) {
			return w[x] > w[y];
		});
		int ptr = 0;
		for (auto &e : calc) {
			while (ptr < sz(unchanged) && w[unchanged[ptr]] >= ww[e]) {
				dsu.unite(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			dsu.snapshot();
			for (auto &f : toJoin[e - L]) {
				dsu.unite(u[f], v[f]);
			}
			ans[e] = dsu.size(id[e]);
			dsu.rollback();
		}
		for (auto &e : upd) used[id[e]] = 0;
	}
	for (auto &e : ans) {
		if (e) cout << e << '\n';
	}	
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
	{
		solve();
	}
#ifdef LOCAL
	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 18 ms 1568 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 17 ms 1888 KB Output is correct
6 Correct 13 ms 1628 KB Output is correct
7 Correct 16 ms 1912 KB Output is correct
8 Correct 18 ms 1608 KB Output is correct
9 Correct 17 ms 1944 KB Output is correct
10 Correct 18 ms 1620 KB Output is correct
11 Correct 19 ms 1652 KB Output is correct
12 Correct 23 ms 1756 KB Output is correct
13 Correct 22 ms 1708 KB Output is correct
14 Correct 21 ms 1640 KB Output is correct
15 Correct 22 ms 1748 KB Output is correct
16 Correct 17 ms 2004 KB Output is correct
17 Correct 18 ms 1840 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 5420 KB Output is correct
2 Correct 1391 ms 6016 KB Output is correct
3 Correct 1401 ms 5988 KB Output is correct
4 Correct 1392 ms 5948 KB Output is correct
5 Correct 1422 ms 5976 KB Output is correct
6 Correct 1603 ms 6428 KB Output is correct
7 Correct 1603 ms 6348 KB Output is correct
8 Correct 1578 ms 6400 KB Output is correct
9 Correct 34 ms 3216 KB Output is correct
10 Correct 697 ms 6340 KB Output is correct
11 Correct 703 ms 6272 KB Output is correct
12 Correct 1308 ms 5568 KB Output is correct
13 Correct 1300 ms 6032 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 4720 KB Output is correct
2 Correct 411 ms 4560 KB Output is correct
3 Correct 1002 ms 5540 KB Output is correct
4 Correct 941 ms 5376 KB Output is correct
5 Correct 34 ms 3148 KB Output is correct
6 Correct 996 ms 5340 KB Output is correct
7 Correct 933 ms 5304 KB Output is correct
8 Correct 886 ms 5168 KB Output is correct
9 Correct 828 ms 4676 KB Output is correct
10 Correct 813 ms 4612 KB Output is correct
11 Correct 839 ms 5316 KB Output is correct
12 Correct 792 ms 5308 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2735 ms 5388 KB Output is correct
2 Correct 34 ms 3248 KB Output is correct
3 Correct 268 ms 4016 KB Output is correct
4 Correct 115 ms 3724 KB Output is correct
5 Correct 1316 ms 6036 KB Output is correct
6 Correct 2685 ms 6452 KB Output is correct
7 Correct 1280 ms 6068 KB Output is correct
8 Correct 1236 ms 5044 KB Output is correct
9 Correct 1205 ms 5184 KB Output is correct
10 Correct 1235 ms 5308 KB Output is correct
11 Correct 1993 ms 5732 KB Output is correct
12 Correct 1949 ms 5896 KB Output is correct
13 Correct 2001 ms 5792 KB Output is correct
14 Correct 1154 ms 6216 KB Output is correct
15 Correct 1239 ms 5976 KB Output is correct
16 Correct 2712 ms 6360 KB Output is correct
17 Correct 2715 ms 6244 KB Output is correct
18 Correct 2682 ms 6108 KB Output is correct
19 Correct 2688 ms 6328 KB Output is correct
20 Correct 2224 ms 6100 KB Output is correct
21 Correct 2237 ms 5896 KB Output is correct
22 Correct 2636 ms 6160 KB Output is correct
23 Correct 1461 ms 5680 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 5420 KB Output is correct
2 Correct 1391 ms 6016 KB Output is correct
3 Correct 1401 ms 5988 KB Output is correct
4 Correct 1392 ms 5948 KB Output is correct
5 Correct 1422 ms 5976 KB Output is correct
6 Correct 1603 ms 6428 KB Output is correct
7 Correct 1603 ms 6348 KB Output is correct
8 Correct 1578 ms 6400 KB Output is correct
9 Correct 34 ms 3216 KB Output is correct
10 Correct 697 ms 6340 KB Output is correct
11 Correct 703 ms 6272 KB Output is correct
12 Correct 1308 ms 5568 KB Output is correct
13 Correct 1300 ms 6032 KB Output is correct
14 Correct 942 ms 4720 KB Output is correct
15 Correct 411 ms 4560 KB Output is correct
16 Correct 1002 ms 5540 KB Output is correct
17 Correct 941 ms 5376 KB Output is correct
18 Correct 34 ms 3148 KB Output is correct
19 Correct 996 ms 5340 KB Output is correct
20 Correct 933 ms 5304 KB Output is correct
21 Correct 886 ms 5168 KB Output is correct
22 Correct 828 ms 4676 KB Output is correct
23 Correct 813 ms 4612 KB Output is correct
24 Correct 839 ms 5316 KB Output is correct
25 Correct 792 ms 5308 KB Output is correct
26 Correct 1395 ms 6024 KB Output is correct
27 Correct 1573 ms 6388 KB Output is correct
28 Correct 1489 ms 6044 KB Output is correct
29 Correct 1316 ms 5680 KB Output is correct
30 Correct 1521 ms 6372 KB Output is correct
31 Correct 1535 ms 6144 KB Output is correct
32 Correct 1551 ms 6368 KB Output is correct
33 Correct 1458 ms 5880 KB Output is correct
34 Correct 1462 ms 5908 KB Output is correct
35 Correct 1470 ms 5956 KB Output is correct
36 Correct 1324 ms 5776 KB Output is correct
37 Correct 1327 ms 5996 KB Output is correct
38 Correct 1341 ms 5732 KB Output is correct
39 Correct 1275 ms 5196 KB Output is correct
40 Correct 1262 ms 5372 KB Output is correct
41 Correct 1272 ms 5372 KB Output is correct
42 Correct 1234 ms 6040 KB Output is correct
43 Correct 1230 ms 6168 KB Output is correct
44 Correct 1207 ms 6024 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 18 ms 1568 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 17 ms 1888 KB Output is correct
6 Correct 13 ms 1628 KB Output is correct
7 Correct 16 ms 1912 KB Output is correct
8 Correct 18 ms 1608 KB Output is correct
9 Correct 17 ms 1944 KB Output is correct
10 Correct 18 ms 1620 KB Output is correct
11 Correct 19 ms 1652 KB Output is correct
12 Correct 23 ms 1756 KB Output is correct
13 Correct 22 ms 1708 KB Output is correct
14 Correct 21 ms 1640 KB Output is correct
15 Correct 22 ms 1748 KB Output is correct
16 Correct 17 ms 2004 KB Output is correct
17 Correct 18 ms 1840 KB Output is correct
18 Correct 1427 ms 5420 KB Output is correct
19 Correct 1391 ms 6016 KB Output is correct
20 Correct 1401 ms 5988 KB Output is correct
21 Correct 1392 ms 5948 KB Output is correct
22 Correct 1422 ms 5976 KB Output is correct
23 Correct 1603 ms 6428 KB Output is correct
24 Correct 1603 ms 6348 KB Output is correct
25 Correct 1578 ms 6400 KB Output is correct
26 Correct 34 ms 3216 KB Output is correct
27 Correct 697 ms 6340 KB Output is correct
28 Correct 703 ms 6272 KB Output is correct
29 Correct 1308 ms 5568 KB Output is correct
30 Correct 1300 ms 6032 KB Output is correct
31 Correct 942 ms 4720 KB Output is correct
32 Correct 411 ms 4560 KB Output is correct
33 Correct 1002 ms 5540 KB Output is correct
34 Correct 941 ms 5376 KB Output is correct
35 Correct 34 ms 3148 KB Output is correct
36 Correct 996 ms 5340 KB Output is correct
37 Correct 933 ms 5304 KB Output is correct
38 Correct 886 ms 5168 KB Output is correct
39 Correct 828 ms 4676 KB Output is correct
40 Correct 813 ms 4612 KB Output is correct
41 Correct 839 ms 5316 KB Output is correct
42 Correct 792 ms 5308 KB Output is correct
43 Correct 2735 ms 5388 KB Output is correct
44 Correct 34 ms 3248 KB Output is correct
45 Correct 268 ms 4016 KB Output is correct
46 Correct 115 ms 3724 KB Output is correct
47 Correct 1316 ms 6036 KB Output is correct
48 Correct 2685 ms 6452 KB Output is correct
49 Correct 1280 ms 6068 KB Output is correct
50 Correct 1236 ms 5044 KB Output is correct
51 Correct 1205 ms 5184 KB Output is correct
52 Correct 1235 ms 5308 KB Output is correct
53 Correct 1993 ms 5732 KB Output is correct
54 Correct 1949 ms 5896 KB Output is correct
55 Correct 2001 ms 5792 KB Output is correct
56 Correct 1154 ms 6216 KB Output is correct
57 Correct 1239 ms 5976 KB Output is correct
58 Correct 2712 ms 6360 KB Output is correct
59 Correct 2715 ms 6244 KB Output is correct
60 Correct 2682 ms 6108 KB Output is correct
61 Correct 2688 ms 6328 KB Output is correct
62 Correct 2224 ms 6100 KB Output is correct
63 Correct 2237 ms 5896 KB Output is correct
64 Correct 2636 ms 6160 KB Output is correct
65 Correct 1461 ms 5680 KB Output is correct
66 Correct 1395 ms 6024 KB Output is correct
67 Correct 1573 ms 6388 KB Output is correct
68 Correct 1489 ms 6044 KB Output is correct
69 Correct 1316 ms 5680 KB Output is correct
70 Correct 1521 ms 6372 KB Output is correct
71 Correct 1535 ms 6144 KB Output is correct
72 Correct 1551 ms 6368 KB Output is correct
73 Correct 1458 ms 5880 KB Output is correct
74 Correct 1462 ms 5908 KB Output is correct
75 Correct 1470 ms 5956 KB Output is correct
76 Correct 1324 ms 5776 KB Output is correct
77 Correct 1327 ms 5996 KB Output is correct
78 Correct 1341 ms 5732 KB Output is correct
79 Correct 1275 ms 5196 KB Output is correct
80 Correct 1262 ms 5372 KB Output is correct
81 Correct 1272 ms 5372 KB Output is correct
82 Correct 1234 ms 6040 KB Output is correct
83 Correct 1230 ms 6168 KB Output is correct
84 Correct 1207 ms 6024 KB Output is correct
85 Correct 2876 ms 7000 KB Output is correct
86 Correct 285 ms 5408 KB Output is correct
87 Correct 125 ms 5968 KB Output is correct
88 Correct 1439 ms 8748 KB Output is correct
89 Correct 2840 ms 10280 KB Output is correct
90 Correct 1420 ms 8868 KB Output is correct
91 Correct 1468 ms 7948 KB Output is correct
92 Correct 1433 ms 7924 KB Output is correct
93 Correct 1652 ms 8172 KB Output is correct
94 Correct 2169 ms 9020 KB Output is correct
95 Correct 2157 ms 9208 KB Output is correct
96 Correct 2268 ms 9264 KB Output is correct
97 Correct 1422 ms 7756 KB Output is correct
98 Correct 1375 ms 8556 KB Output is correct
99 Correct 2900 ms 10136 KB Output is correct
100 Correct 2906 ms 10068 KB Output is correct
101 Correct 2937 ms 10256 KB Output is correct
102 Correct 2910 ms 10012 KB Output is correct
103 Correct 2517 ms 9596 KB Output is correct
104 Correct 2512 ms 9408 KB Output is correct
105 Correct 2382 ms 9420 KB Output is correct
106 Correct 2045 ms 9152 KB Output is correct
107 Correct 2307 ms 8616 KB Output is correct
108 Correct 2760 ms 10052 KB Output is correct
109 Correct 1662 ms 8192 KB Output is correct