oj.uz

Submission #263616

# Submission time Handle Problem Language Result Execution time Memory
263616 2020-08-13T22:03:56 Z hanagasumi Bridges (APIO19_bridges) C++17
100 / 100
 2985 ms 11688 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef long double ld;

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

struct zap {
	int tp, id, w;
};


vector<int> p;
vector<int> sz;

int findp(int v) {
	if(p[v] == v) 
		return v;
	return findp(p[v]);
}

int getp(int v) {
	if(p[v] == v) 
		return v;
	p[v] = getp(p[v]);
	return p[v];
}

void merge(int a, int b) {
	a = getp(a), b = getp(b);
	if(a == b) 
		return;
	if(sz[a] < sz[b]) 
		swap(a, b);
	p[b] = a;
	sz[a] += sz[b];
}

void merge(int a, int b, vector<pair<int, pair<int, int>>>& otk) {
	a = findp(a), b = findp(b);
	if(a == b)
		return;
	if(sz[a] < sz[b]) 
		swap(a, b);
	otk.pb({b, {p[b], sz[b]}});
	otk.pb({a, {p[a], sz[a]}});
	p[b] = a;
	sz[a] += sz[b];
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m, q;
	cin >> n >> m;
	vector<edge> e;
	vector<vector<int>> g(n);
	p = vector<int> (n);
	sz = vector<int> (n);
	vector<zap> z;
	int k = 800;
	int maxk;
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		e.pb({a, b, w});
	}

	cin >> q;
	vector<int> ans(q, -1);
	maxk = (q - 1) / k;
	for (int qq = 0; qq < q; qq++) {
		int tp, id, w;
		cin >> tp >> id >> w;
		id--;
		z.pb({tp, id, w});
	}

	for (int i = 0; i <= maxk; i++) {
		int end = min(q, (i + 1) * k), beg = i * k;
		for (int i = 0; i < n; i++) 
			p[i] = i, sz[i] = 1;
		vector<bool> used(m, 1);
		vector<pair<int, pair<int, int>>> ask;
		vector<int> bad;

		for (int i = beg; i < end; i++) {
			if(z[i].tp == 2) {
				ask.pb({z[i].w, {0, i}});
				continue;
			}
			used[z[i].id] = 0;
		}
		for (int i = 0; i < m; i++) {
			if(!used[i]) {
				bad.pb(i);
				continue;
			}
			ask.pb({e[i].w, {1, i}});
		}
		// for (auto x : bad) 
		// 	cout << x << " ";
		// cout << endl;
		sort(all(ask)); 
		reverse(all(ask));
		
		for (int i = 0; i < len(ask); i++) {
			// cout << "SOB: " << ask[i].ft << " " << ask[i].sc.ft << " " << ask[i].sc.sc << endl;
			if(ask[i].sc.ft == 1) {
				merge(e[ask[i].sc.sc].v, e[ask[i].sc.sc].u);
				continue;
			}
			int num = ask[i].sc.sc;
			vector<pair<int, int>> eo;
			vector<pair<int, pair<int, int>>> po;
			for (int i = beg; i < num; i++) {
				if(z[i].tp == 2) 
					continue;
				eo.pb({z[i].id, e[z[i].id].w});
				e[z[i].id].w = z[i].w;
			}
			for (auto x : bad) {
				if(e[x].w < z[num].w) 
					continue;
				merge(e[x].u, e[x].v, po);
			}
			ans[num] = sz[findp(z[num].id)];
			reverse(all(po));
			reverse(all(eo));
			for (auto x : eo) {
				e[x.ft].w = x.sc;
			}
			for (auto x : po) {
				p[x.ft] = x.sc.ft;
				sz[x.ft] = x.sc.sc;
			}
		}
		for (int i = beg; i < end; i++) {
			if(z[i].tp == 2)
				continue;
			e[z[i].id].w = z[i].w;
		}
	}


	for (int i = 0; i < q; i++) {
		// cout << ans[i] << " ";
		if(ans[i] == -1) 
			continue;
		cout << ans[i] << '\n';
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 35 ms 716 KB Output is correct
4 Correct 7 ms 704 KB Output is correct
5 Correct 29 ms 700 KB Output is correct
6 Correct 26 ms 708 KB Output is correct
7 Correct 34 ms 696 KB Output is correct
8 Correct 34 ms 696 KB Output is correct
9 Correct 49 ms 696 KB Output is correct
10 Correct 37 ms 700 KB Output is correct
11 Correct 35 ms 696 KB Output is correct
12 Correct 38 ms 700 KB Output is correct
13 Correct 40 ms 700 KB Output is correct
14 Correct 39 ms 700 KB Output is correct
15 Correct 36 ms 700 KB Output is correct
16 Correct 37 ms 696 KB Output is correct
17 Correct 37 ms 696 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1970 ms 5744 KB Output is correct
2 Correct 1887 ms 5884 KB Output is correct
3 Correct 1921 ms 5636 KB Output is correct
4 Correct 1922 ms 5920 KB Output is correct
5 Correct 2004 ms 5724 KB Output is correct
6 Correct 2610 ms 5724 KB Output is correct
7 Correct 2653 ms 5844 KB Output is correct
8 Correct 2613 ms 5832 KB Output is correct
9 Correct 62 ms 2424 KB Output is correct
10 Correct 1958 ms 5632 KB Output is correct
11 Correct 1917 ms 5684 KB Output is correct
12 Correct 1742 ms 5720 KB Output is correct
13 Correct 1580 ms 5656 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 4904 KB Output is correct
2 Correct 1145 ms 2872 KB Output is correct
3 Correct 1708 ms 4556 KB Output is correct
4 Correct 1491 ms 4708 KB Output is correct
5 Correct 61 ms 2424 KB Output is correct
6 Correct 1639 ms 4768 KB Output is correct
7 Correct 1425 ms 4912 KB Output is correct
8 Correct 1280 ms 4544 KB Output is correct
9 Correct 1141 ms 4560 KB Output is correct
10 Correct 1067 ms 4600 KB Output is correct
11 Correct 948 ms 4204 KB Output is correct
12 Correct 872 ms 4204 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2224 ms 7632 KB Output is correct
2 Correct 68 ms 2424 KB Output is correct
3 Correct 235 ms 4576 KB Output is correct
4 Correct 206 ms 4568 KB Output is correct
5 Correct 2287 ms 7740 KB Output is correct
6 Correct 2274 ms 7672 KB Output is correct
7 Correct 2280 ms 7832 KB Output is correct
8 Correct 1155 ms 5692 KB Output is correct
9 Correct 1160 ms 5940 KB Output is correct
10 Correct 1203 ms 5600 KB Output is correct
11 Correct 1840 ms 6912 KB Output is correct
12 Correct 1820 ms 7252 KB Output is correct
13 Correct 1865 ms 7364 KB Output is correct
14 Correct 1990 ms 7768 KB Output is correct
15 Correct 2145 ms 7612 KB Output is correct
16 Correct 2370 ms 7740 KB Output is correct
17 Correct 2351 ms 7732 KB Output is correct
18 Correct 2366 ms 7784 KB Output is correct
19 Correct 2281 ms 7436 KB Output is correct
20 Correct 1992 ms 7068 KB Output is correct
21 Correct 1995 ms 7252 KB Output is correct
22 Correct 2266 ms 7696 KB Output is correct
23 Correct 2087 ms 7052 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1970 ms 5744 KB Output is correct
2 Correct 1887 ms 5884 KB Output is correct
3 Correct 1921 ms 5636 KB Output is correct
4 Correct 1922 ms 5920 KB Output is correct
5 Correct 2004 ms 5724 KB Output is correct
6 Correct 2610 ms 5724 KB Output is correct
7 Correct 2653 ms 5844 KB Output is correct
8 Correct 2613 ms 5832 KB Output is correct
9 Correct 62 ms 2424 KB Output is correct
10 Correct 1958 ms 5632 KB Output is correct
11 Correct 1917 ms 5684 KB Output is correct
12 Correct 1742 ms 5720 KB Output is correct
13 Correct 1580 ms 5656 KB Output is correct
14 Correct 1500 ms 4904 KB Output is correct
15 Correct 1145 ms 2872 KB Output is correct
16 Correct 1708 ms 4556 KB Output is correct
17 Correct 1491 ms 4708 KB Output is correct
18 Correct 61 ms 2424 KB Output is correct
19 Correct 1639 ms 4768 KB Output is correct
20 Correct 1425 ms 4912 KB Output is correct
21 Correct 1280 ms 4544 KB Output is correct
22 Correct 1141 ms 4560 KB Output is correct
23 Correct 1067 ms 4600 KB Output is correct
24 Correct 948 ms 4204 KB Output is correct
25 Correct 872 ms 4204 KB Output is correct
26 Correct 1997 ms 5748 KB Output is correct
27 Correct 2269 ms 5752 KB Output is correct
28 Correct 2056 ms 5732 KB Output is correct
29 Correct 1558 ms 5600 KB Output is correct
30 Correct 2183 ms 5732 KB Output is correct
31 Correct 2241 ms 5828 KB Output is correct
32 Correct 2260 ms 5832 KB Output is correct
33 Correct 2035 ms 5484 KB Output is correct
34 Correct 1991 ms 5904 KB Output is correct
35 Correct 2056 ms 5652 KB Output is correct
36 Correct 1674 ms 5692 KB Output is correct
37 Correct 1685 ms 5596 KB Output is correct
38 Correct 1629 ms 5712 KB Output is correct
39 Correct 1401 ms 5652 KB Output is correct
40 Correct 1363 ms 5632 KB Output is correct
41 Correct 1374 ms 5720 KB Output is correct
42 Correct 1292 ms 5684 KB Output is correct
43 Correct 1297 ms 5856 KB Output is correct
44 Correct 1259 ms 5536 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 35 ms 716 KB Output is correct
4 Correct 7 ms 704 KB Output is correct
5 Correct 29 ms 700 KB Output is correct
6 Correct 26 ms 708 KB Output is correct
7 Correct 34 ms 696 KB Output is correct
8 Correct 34 ms 696 KB Output is correct
9 Correct 49 ms 696 KB Output is correct
10 Correct 37 ms 700 KB Output is correct
11 Correct 35 ms 696 KB Output is correct
12 Correct 38 ms 700 KB Output is correct
13 Correct 40 ms 700 KB Output is correct
14 Correct 39 ms 700 KB Output is correct
15 Correct 36 ms 700 KB Output is correct
16 Correct 37 ms 696 KB Output is correct
17 Correct 37 ms 696 KB Output is correct
18 Correct 1970 ms 5744 KB Output is correct
19 Correct 1887 ms 5884 KB Output is correct
20 Correct 1921 ms 5636 KB Output is correct
21 Correct 1922 ms 5920 KB Output is correct
22 Correct 2004 ms 5724 KB Output is correct
23 Correct 2610 ms 5724 KB Output is correct
24 Correct 2653 ms 5844 KB Output is correct
25 Correct 2613 ms 5832 KB Output is correct
26 Correct 62 ms 2424 KB Output is correct
27 Correct 1958 ms 5632 KB Output is correct
28 Correct 1917 ms 5684 KB Output is correct
29 Correct 1742 ms 5720 KB Output is correct
30 Correct 1580 ms 5656 KB Output is correct
31 Correct 1500 ms 4904 KB Output is correct
32 Correct 1145 ms 2872 KB Output is correct
33 Correct 1708 ms 4556 KB Output is correct
34 Correct 1491 ms 4708 KB Output is correct
35 Correct 61 ms 2424 KB Output is correct
36 Correct 1639 ms 4768 KB Output is correct
37 Correct 1425 ms 4912 KB Output is correct
38 Correct 1280 ms 4544 KB Output is correct
39 Correct 1141 ms 4560 KB Output is correct
40 Correct 1067 ms 4600 KB Output is correct
41 Correct 948 ms 4204 KB Output is correct
42 Correct 872 ms 4204 KB Output is correct
43 Correct 2224 ms 7632 KB Output is correct
44 Correct 68 ms 2424 KB Output is correct
45 Correct 235 ms 4576 KB Output is correct
46 Correct 206 ms 4568 KB Output is correct
47 Correct 2287 ms 7740 KB Output is correct
48 Correct 2274 ms 7672 KB Output is correct
49 Correct 2280 ms 7832 KB Output is correct
50 Correct 1155 ms 5692 KB Output is correct
51 Correct 1160 ms 5940 KB Output is correct
52 Correct 1203 ms 5600 KB Output is correct
53 Correct 1840 ms 6912 KB Output is correct
54 Correct 1820 ms 7252 KB Output is correct
55 Correct 1865 ms 7364 KB Output is correct
56 Correct 1990 ms 7768 KB Output is correct
57 Correct 2145 ms 7612 KB Output is correct
58 Correct 2370 ms 7740 KB Output is correct
59 Correct 2351 ms 7732 KB Output is correct
60 Correct 2366 ms 7784 KB Output is correct
61 Correct 2281 ms 7436 KB Output is correct
62 Correct 1992 ms 7068 KB Output is correct
63 Correct 1995 ms 7252 KB Output is correct
64 Correct 2266 ms 7696 KB Output is correct
65 Correct 2087 ms 7052 KB Output is correct
66 Correct 1997 ms 5748 KB Output is correct
67 Correct 2269 ms 5752 KB Output is correct
68 Correct 2056 ms 5732 KB Output is correct
69 Correct 1558 ms 5600 KB Output is correct
70 Correct 2183 ms 5732 KB Output is correct
71 Correct 2241 ms 5828 KB Output is correct
72 Correct 2260 ms 5832 KB Output is correct
73 Correct 2035 ms 5484 KB Output is correct
74 Correct 1991 ms 5904 KB Output is correct
75 Correct 2056 ms 5652 KB Output is correct
76 Correct 1674 ms 5692 KB Output is correct
77 Correct 1685 ms 5596 KB Output is correct
78 Correct 1629 ms 5712 KB Output is correct
79 Correct 1401 ms 5652 KB Output is correct
80 Correct 1363 ms 5632 KB Output is correct
81 Correct 1374 ms 5720 KB Output is correct
82 Correct 1292 ms 5684 KB Output is correct
83 Correct 1297 ms 5856 KB Output is correct
84 Correct 1259 ms 5536 KB Output is correct
85 Correct 2815 ms 11676 KB Output is correct
86 Correct 268 ms 6532 KB Output is correct
87 Correct 242 ms 6548 KB Output is correct
88 Correct 2863 ms 9900 KB Output is correct
89 Correct 2828 ms 11540 KB Output is correct
90 Correct 2793 ms 9884 KB Output is correct
91 Correct 2070 ms 8584 KB Output is correct
92 Correct 2054 ms 8740 KB Output is correct
93 Correct 2637 ms 8524 KB Output is correct
94 Correct 2491 ms 10240 KB Output is correct
95 Correct 2516 ms 10324 KB Output is correct
96 Correct 2506 ms 10356 KB Output is correct
97 Correct 2501 ms 10064 KB Output is correct
98 Correct 2432 ms 10008 KB Output is correct
99 Correct 2900 ms 11292 KB Output is correct
100 Correct 2814 ms 11600 KB Output is correct
101 Correct 2948 ms 11592 KB Output is correct
102 Correct 2985 ms 11688 KB Output is correct
103 Correct 2556 ms 10768 KB Output is correct
104 Correct 2556 ms 10560 KB Output is correct
105 Correct 2266 ms 10828 KB Output is correct
106 Correct 1889 ms 10236 KB Output is correct
107 Correct 2241 ms 10824 KB Output is correct
108 Correct 2762 ms 11352 KB Output is correct
109 Correct 2675 ms 9176 KB Output is correct