oj.uz

Submission #264936

# Submission time Handle Problem Language Result Execution time Memory
264936 2020-08-14T11:25:22 Z dimash241 Bridges (APIO19_bridges) C++17
44 / 100
 3000 ms 134180 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 = 900;
 
	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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 39 ms 508 KB Output is correct
4 Correct 5 ms 704 KB Output is correct
5 Correct 20 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 21 ms 384 KB Output is correct
8 Correct 21 ms 384 KB Output is correct
9 Correct 24 ms 384 KB Output is correct
10 Correct 22 ms 384 KB Output is correct
11 Correct 21 ms 384 KB Output is correct
12 Correct 23 ms 384 KB Output is correct
13 Correct 31 ms 384 KB Output is correct
14 Correct 27 ms 512 KB Output is correct
15 Correct 22 ms 512 KB Output is correct
16 Correct 22 ms 384 KB Output is correct
17 Correct 23 ms 480 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 134032 KB Output is correct
2 Correct 2001 ms 134116 KB Output is correct
3 Correct 1998 ms 134104 KB Output is correct
4 Correct 2077 ms 134056 KB Output is correct
5 Correct 1990 ms 133976 KB Output is correct
6 Execution timed out 3053 ms 134180 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1687 ms 67732 KB Output is correct
2 Correct 1517 ms 17624 KB Output is correct
3 Correct 2045 ms 67608 KB Output is correct
4 Correct 1653 ms 67616 KB Output is correct
5 Correct 43 ms 2416 KB Output is correct
6 Correct 1931 ms 67836 KB Output is correct
7 Correct 1514 ms 67780 KB Output is correct
8 Correct 1306 ms 67744 KB Output is correct
9 Correct 2791 ms 18648 KB Output is correct
10 Correct 2092 ms 18388 KB Output is correct
11 Correct 1018 ms 133352 KB Output is correct
12 Correct 868 ms 133464 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 7396 KB Output is correct
2 Correct 44 ms 2424 KB Output is correct
3 Correct 47 ms 3048 KB Output is correct
4 Correct 40 ms 3052 KB Output is correct
5 Correct 80 ms 7400 KB Output is correct
6 Correct 106 ms 7524 KB Output is correct
7 Correct 84 ms 7396 KB Output is correct
8 Correct 80 ms 6376 KB Output is correct
9 Correct 77 ms 6372 KB Output is correct
10 Correct 75 ms 6380 KB Output is correct
11 Correct 89 ms 7020 KB Output is correct
12 Correct 89 ms 7044 KB Output is correct
13 Correct 89 ms 7012 KB Output is correct
14 Correct 80 ms 7520 KB Output is correct
15 Correct 85 ms 7476 KB Output is correct
16 Correct 105 ms 7396 KB Output is correct
17 Correct 105 ms 7428 KB Output is correct
18 Correct 99 ms 7396 KB Output is correct
19 Correct 102 ms 7400 KB Output is correct
20 Correct 92 ms 7184 KB Output is correct
21 Correct 94 ms 7140 KB Output is correct
22 Correct 112 ms 7396 KB Output is correct
23 Correct 94 ms 7052 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 134032 KB Output is correct
2 Correct 2001 ms 134116 KB Output is correct
3 Correct 1998 ms 134104 KB Output is correct
4 Correct 2077 ms 134056 KB Output is correct
5 Correct 1990 ms 133976 KB Output is correct
6 Execution timed out 3053 ms 134180 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 39 ms 508 KB Output is correct
4 Correct 5 ms 704 KB Output is correct
5 Correct 20 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 21 ms 384 KB Output is correct
8 Correct 21 ms 384 KB Output is correct
9 Correct 24 ms 384 KB Output is correct
10 Correct 22 ms 384 KB Output is correct
11 Correct 21 ms 384 KB Output is correct
12 Correct 23 ms 384 KB Output is correct
13 Correct 31 ms 384 KB Output is correct
14 Correct 27 ms 512 KB Output is correct
15 Correct 22 ms 512 KB Output is correct
16 Correct 22 ms 384 KB Output is correct
17 Correct 23 ms 480 KB Output is correct
18 Correct 1965 ms 134032 KB Output is correct
19 Correct 2001 ms 134116 KB Output is correct
20 Correct 1998 ms 134104 KB Output is correct
21 Correct 2077 ms 134056 KB Output is correct
22 Correct 1990 ms 133976 KB Output is correct
23 Execution timed out 3053 ms 134180 KB Time limit exceeded
24 Halted 0 ms 0 KB -