oj.uz

Submission #129781

# Submission time Handle Problem Language Result Execution time Memory
129781 2019-07-13T08:19:33 Z pr3pony Bridges (APIO19_bridges) C++14
44 / 100
 3000 ms 267496 KB 
// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n, m;
	cin >> n >> m;
	vector<pair<pii, int>> edges;
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		edges.push_back({{a, b}, c});
	}

	const int SZ = 500;

	int q;
	cin >> q;
	vector<int> ans(q, -1);
	vector<bool> changed(m);
	vector<pair<pii, int>> actions;
	vector<pair<pii, int>> questions;
	vector<int> dsu(n);
	vector<int> sz(n);
	vector<pair<int*, int>> dsu_changes;
	auto get_root = [&](int v, int t) {
		int mem = v;
		while (dsu[v] != v) {
			v = dsu[v];
		}
		if (t) {
			while (dsu[mem] != mem) {
				int tmp = dsu[mem];
				dsu[mem] = v;
				mem = tmp;
			}
		}
		return v;
	};

	auto unite = [&](int a, int b, int t) {
		a = get_root(a, t);
		b = get_root(b, t);
		if (a == b) {
			return;
		}
		if (sz[a] < sz[b]) {
			swap(a, b);
		}
		dsu_changes.push_back({&sz[a], sz[a]});
		sz[a] += sz[b];
		dsu_changes.push_back({&dsu[b], dsu[b]});
		dsu[b] = a;
	};

	vector<int> static_edges;
	vector<int> not_static_edges;

	for (int i = 0; i < q; ++i) {
		int t;
		cin >> t;
		if (t == 1) {
			int ind, c;
			cin >> ind >> c;
			--ind;
			changed[ind] = true;
			actions.push_back({{ind, c}, i});
		} else {
			int v, w;
			cin >> v >> w;
			--v;
			questions.push_back({{w, v}, i});
		}
		if (i == q - 1 || szof(actions) == SZ) {
			sort(questions.begin(), questions.end());
			reverse(questions.begin(), questions.end());
			iota(dsu.begin(), dsu.end(), 0);
			fill(sz.begin(), sz.end(), 1);

			static_edges.clear();
			not_static_edges.clear();

			for (int j = 0; j < m; ++j) {
				if (!changed[j]) {
					static_edges.push_back(j);
				} else {
					not_static_edges.push_back(j);
				}
			}

			sort(static_edges.begin(), static_edges.end(), [&](int a, int b){
				return edges[a].ss > edges[b].ss;
			});

			vector<int> last(m);

			int cnt_static_edges = 0;
			for (auto q : questions) {
				while (cnt_static_edges < szof(static_edges) && edges[static_edges[cnt_static_edges]].ss >= q.ff.ff) {
					unite(edges[static_edges[cnt_static_edges]].ff.ff, edges[static_edges[cnt_static_edges]].ff.ss, 1);
					++cnt_static_edges;
				}
				int mem = szof(dsu_changes);
				
				for (int e : not_static_edges) {
					last[e] = edges[e].ss;
				}
				for (auto act : actions) {
					if (act.ss > q.ss) {
						break;
					}
					last[act.ff.ff] = act.ff.ss;
				}
				for (int e : not_static_edges) {
					if (last[e] >= q.ff.ff) {
						unite(edges[e].ff.ff, edges[e].ff.ss, 0);
					}
				}
				ans[q.ss] = sz[get_root(q.ff.ss, 0)];
				while (szof(dsu_changes) > mem) {
					*dsu_changes.back().ff = dsu_changes.back().ss;
					dsu_changes.pop_back();
				}
			}

			for (auto act : actions) {
				edges[act.ff.ff].ss = act.ff.ss;
			}

			actions.clear();
			questions.clear();
			fill(changed.begin(), changed.end(), 0);
		}
	}


	for (int num : ans) {
		if (num != -1) {
			cout << num << "\n";
		}
	}
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 28 ms 760 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 15 ms 632 KB Output is correct
7 Correct 18 ms 476 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 18 ms 504 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 23 ms 632 KB Output is correct
14 Correct 22 ms 632 KB Output is correct
15 Correct 19 ms 632 KB Output is correct
16 Correct 19 ms 504 KB Output is correct
17 Correct 19 ms 504 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2114 ms 265744 KB Output is correct
2 Correct 2113 ms 266148 KB Output is correct
3 Correct 2072 ms 266212 KB Output is correct
4 Correct 2104 ms 266160 KB Output is correct
5 Correct 2064 ms 265968 KB Output is correct
6 Correct 2745 ms 265912 KB Output is correct
7 Correct 2796 ms 267432 KB Output is correct
8 Correct 2812 ms 267496 KB Output is correct
9 Correct 51 ms 3692 KB Output is correct
10 Correct 1699 ms 267092 KB Output is correct
11 Correct 1640 ms 266992 KB Output is correct
12 Execution timed out 3040 ms 37432 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1580 ms 134076 KB Output is correct
2 Correct 964 ms 34548 KB Output is correct
3 Correct 1720 ms 134252 KB Output is correct
4 Correct 1556 ms 134132 KB Output is correct
5 Correct 51 ms 3056 KB Output is correct
6 Correct 1654 ms 134404 KB Output is correct
7 Correct 1458 ms 134284 KB Output is correct
8 Correct 1297 ms 134212 KB Output is correct
9 Correct 1745 ms 35920 KB Output is correct
10 Correct 1265 ms 37076 KB Output is correct
11 Correct 1585 ms 266820 KB Output is correct
12 Correct 1493 ms 266716 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9104 KB Output is correct
2 Correct 51 ms 3312 KB Output is correct
3 Correct 57 ms 4588 KB Output is correct
4 Correct 47 ms 4712 KB Output is correct
5 Correct 98 ms 9108 KB Output is correct
6 Correct 117 ms 9060 KB Output is correct
7 Correct 97 ms 9064 KB Output is correct
8 Correct 91 ms 8140 KB Output is correct
9 Correct 89 ms 8040 KB Output is correct
10 Correct 90 ms 8008 KB Output is correct
11 Correct 103 ms 8540 KB Output is correct
12 Correct 104 ms 8552 KB Output is correct
13 Correct 102 ms 8552 KB Output is correct
14 Correct 94 ms 9064 KB Output is correct
15 Correct 94 ms 9064 KB Output is correct
16 Correct 118 ms 9064 KB Output is correct
17 Correct 122 ms 9020 KB Output is correct
18 Correct 118 ms 9060 KB Output is correct
19 Correct 116 ms 9064 KB Output is correct
20 Correct 106 ms 8792 KB Output is correct
21 Correct 106 ms 8796 KB Output is correct
22 Correct 113 ms 8936 KB Output is correct
23 Correct 93 ms 8676 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2114 ms 265744 KB Output is correct
2 Correct 2113 ms 266148 KB Output is correct
3 Correct 2072 ms 266212 KB Output is correct
4 Correct 2104 ms 266160 KB Output is correct
5 Correct 2064 ms 265968 KB Output is correct
6 Correct 2745 ms 265912 KB Output is correct
7 Correct 2796 ms 267432 KB Output is correct
8 Correct 2812 ms 267496 KB Output is correct
9 Correct 51 ms 3692 KB Output is correct
10 Correct 1699 ms 267092 KB Output is correct
11 Correct 1640 ms 266992 KB Output is correct
12 Execution timed out 3040 ms 37432 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 28 ms 760 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 15 ms 632 KB Output is correct
7 Correct 18 ms 476 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 18 ms 504 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 23 ms 632 KB Output is correct
14 Correct 22 ms 632 KB Output is correct
15 Correct 19 ms 632 KB Output is correct
16 Correct 19 ms 504 KB Output is correct
17 Correct 19 ms 504 KB Output is correct
18 Correct 2114 ms 265744 KB Output is correct
19 Correct 2113 ms 266148 KB Output is correct
20 Correct 2072 ms 266212 KB Output is correct
21 Correct 2104 ms 266160 KB Output is correct
22 Correct 2064 ms 265968 KB Output is correct
23 Correct 2745 ms 265912 KB Output is correct
24 Correct 2796 ms 267432 KB Output is correct
25 Correct 2812 ms 267496 KB Output is correct
26 Correct 51 ms 3692 KB Output is correct
27 Correct 1699 ms 267092 KB Output is correct
28 Correct 1640 ms 266992 KB Output is correct
29 Execution timed out 3040 ms 37432 KB Time limit exceeded
30 Halted 0 ms 0 KB -