oj.uz

Submission #771475

# Submission time Handle Problem Language Result Execution time Memory
771475 2023-07-03T04:16:31 Z siewjh Bridges (APIO19_bridges) C++17
100 / 100
 2220 ms 9816 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
const int MAXE = 100005;
int par[MAXN], sz[MAXN];
bool ch[MAXE];
vector<pair<int, int>> jst;
int root(int x){
	if (par[x] == -1) return x;
	else return root(par[x]);
}
void join(int a, int b){
	int ra = root(a), rb = root(b);
	if (ra == rb) return;
	if (sz[ra] < sz[rb]) swap(ra, rb); // ra larger
	par[rb] = ra;
	sz[ra] += sz[rb];
	jst.push_back({ra, rb});
}
void rollback(){
	while (!jst.empty()){
		int ra, rb; tie(ra, rb) = jst.back(); jst.pop_back();
		par[rb] = -1;
		sz[ra] -= sz[rb];
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	vector<int> ea(edges + 1), eb(edges + 1), ew(edges + 1);
	for (int i = 1; i <= edges; i++){
		int a, b, w; cin >> a >> b >> w;
		ea[i] = a; eb[i] = b; ew[i] = w;
	}
	int queries; cin >> queries;
	vector<int> qt(queries), qx(queries), qw(queries);
	for (int i = 0; i < queries; i++){
		int typ, ind, w; cin >> typ >> ind >> w;
		qt[i] = typ; qx[i] = ind; qw[i] = w;
	}
	vector<int> ans(queries, -1);
	const int bsz = 600;
	vector<int> dyna[bsz];
	bool ch[MAXE];
	for (int l = 0; l < queries; l += bsz){
		int r = min(l + bsz, queries) - 1;
		fill(par + 1, par + nodes + 1, -1);
		fill(sz + 1, sz + nodes + 1, 1);
		vector<int> qv, stat, chv;
		for (int i = l; i <= r; i++){
			if (qt[i] == 1)
				ch[qx[i]] = 1;
		}
		for (int i = 1; i <= edges; i++){
			if (ch[i]) chv.push_back(i);
			else stat.push_back(i);
		}
		for (int i = l; i <= r; i++){
			int x = qx[i], w = qw[i];
			if (qt[i] == 1) ew[x] = w;
			else{
				qv.push_back(i);
				dyna[i - l].clear();
				for (int eind : chv)
					if (ew[eind] >= w)
						dyna[i - l].push_back(eind);
			}
		}
		sort(stat.begin(), stat.end(), [&](int a, int b){return ew[a] > ew[b];});
		sort(qv.begin(), qv.end(), [&](int a, int b){return qw[a] > qw[b];});
		int stind = 0;
		for (int qind : qv){
			int w = qw[qind], x = qx[qind];
			while (stind != stat.size() && ew[stat[stind]] >= w){
				int eind = stat[stind];
				join(ea[eind], eb[eind]);
				stind++;
			}
			jst.clear();
			for (int eind : dyna[qind - l]) join(ea[eind], eb[eind]);
			ans[qind] = sz[root(x)];
			rollback();
		}
		for (int x : chv) ch[x] = 0;
	}
	for (int i = 0; i < queries; i++)
		if (ans[i] != -1)
			cout << ans[i] << '\n';
	return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    while (stind != stat.size() && ew[stat[stind]] >= w){
      |           ~~~~~~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 14 ms 1364 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 5 ms 908 KB Output is correct
7 Correct 6 ms 944 KB Output is correct
8 Correct 7 ms 852 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 7 ms 852 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 9 ms 976 KB Output is correct
14 Correct 9 ms 980 KB Output is correct
15 Correct 8 ms 852 KB Output is correct
16 Correct 6 ms 852 KB Output is correct
17 Correct 6 ms 852 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 4808 KB Output is correct
2 Correct 1012 ms 4936 KB Output is correct
3 Correct 1037 ms 4800 KB Output is correct
4 Correct 990 ms 4832 KB Output is correct
5 Correct 989 ms 4876 KB Output is correct
6 Correct 1147 ms 5096 KB Output is correct
7 Correct 1147 ms 5152 KB Output is correct
8 Correct 1105 ms 5180 KB Output is correct
9 Correct 25 ms 2124 KB Output is correct
10 Correct 476 ms 5100 KB Output is correct
11 Correct 496 ms 4920 KB Output is correct
12 Correct 973 ms 4232 KB Output is correct
13 Correct 928 ms 6256 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 4292 KB Output is correct
2 Correct 287 ms 3664 KB Output is correct
3 Correct 708 ms 4328 KB Output is correct
4 Correct 716 ms 4292 KB Output is correct
5 Correct 25 ms 2132 KB Output is correct
6 Correct 703 ms 4312 KB Output is correct
7 Correct 656 ms 4308 KB Output is correct
8 Correct 634 ms 4300 KB Output is correct
9 Correct 595 ms 3680 KB Output is correct
10 Correct 579 ms 3400 KB Output is correct
11 Correct 611 ms 5304 KB Output is correct
12 Correct 570 ms 4920 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1977 ms 5040 KB Output is correct
2 Correct 27 ms 3532 KB Output is correct
3 Correct 214 ms 4532 KB Output is correct
4 Correct 89 ms 4864 KB Output is correct
5 Correct 912 ms 7200 KB Output is correct
6 Correct 1974 ms 6804 KB Output is correct
7 Correct 894 ms 7300 KB Output is correct
8 Correct 887 ms 5008 KB Output is correct
9 Correct 887 ms 4984 KB Output is correct
10 Correct 922 ms 5384 KB Output is correct
11 Correct 1469 ms 5732 KB Output is correct
12 Correct 1402 ms 5668 KB Output is correct
13 Correct 1457 ms 6024 KB Output is correct
14 Correct 852 ms 7544 KB Output is correct
15 Correct 878 ms 7476 KB Output is correct
16 Correct 2013 ms 6324 KB Output is correct
17 Correct 2072 ms 6216 KB Output is correct
18 Correct 2032 ms 6404 KB Output is correct
19 Correct 1999 ms 6456 KB Output is correct
20 Correct 1688 ms 6340 KB Output is correct
21 Correct 1653 ms 6504 KB Output is correct
22 Correct 1916 ms 6404 KB Output is correct
23 Correct 1076 ms 6168 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 4808 KB Output is correct
2 Correct 1012 ms 4936 KB Output is correct
3 Correct 1037 ms 4800 KB Output is correct
4 Correct 990 ms 4832 KB Output is correct
5 Correct 989 ms 4876 KB Output is correct
6 Correct 1147 ms 5096 KB Output is correct
7 Correct 1147 ms 5152 KB Output is correct
8 Correct 1105 ms 5180 KB Output is correct
9 Correct 25 ms 2124 KB Output is correct
10 Correct 476 ms 5100 KB Output is correct
11 Correct 496 ms 4920 KB Output is correct
12 Correct 973 ms 4232 KB Output is correct
13 Correct 928 ms 6256 KB Output is correct
14 Correct 722 ms 4292 KB Output is correct
15 Correct 287 ms 3664 KB Output is correct
16 Correct 708 ms 4328 KB Output is correct
17 Correct 716 ms 4292 KB Output is correct
18 Correct 25 ms 2132 KB Output is correct
19 Correct 703 ms 4312 KB Output is correct
20 Correct 656 ms 4308 KB Output is correct
21 Correct 634 ms 4300 KB Output is correct
22 Correct 595 ms 3680 KB Output is correct
23 Correct 579 ms 3400 KB Output is correct
24 Correct 611 ms 5304 KB Output is correct
25 Correct 570 ms 4920 KB Output is correct
26 Correct 1036 ms 5008 KB Output is correct
27 Correct 1120 ms 5044 KB Output is correct
28 Correct 1074 ms 4936 KB Output is correct
29 Correct 988 ms 5000 KB Output is correct
30 Correct 1141 ms 5108 KB Output is correct
31 Correct 1151 ms 4788 KB Output is correct
32 Correct 1110 ms 4924 KB Output is correct
33 Correct 1108 ms 4864 KB Output is correct
34 Correct 1081 ms 4840 KB Output is correct
35 Correct 1069 ms 4856 KB Output is correct
36 Correct 982 ms 4964 KB Output is correct
37 Correct 965 ms 4868 KB Output is correct
38 Correct 968 ms 4816 KB Output is correct
39 Correct 919 ms 3760 KB Output is correct
40 Correct 944 ms 3956 KB Output is correct
41 Correct 926 ms 3784 KB Output is correct
42 Correct 910 ms 5244 KB Output is correct
43 Correct 900 ms 5216 KB Output is correct
44 Correct 889 ms 5364 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 14 ms 1364 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 5 ms 908 KB Output is correct
7 Correct 6 ms 944 KB Output is correct
8 Correct 7 ms 852 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 7 ms 852 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 9 ms 976 KB Output is correct
14 Correct 9 ms 980 KB Output is correct
15 Correct 8 ms 852 KB Output is correct
16 Correct 6 ms 852 KB Output is correct
17 Correct 6 ms 852 KB Output is correct
18 Correct 1008 ms 4808 KB Output is correct
19 Correct 1012 ms 4936 KB Output is correct
20 Correct 1037 ms 4800 KB Output is correct
21 Correct 990 ms 4832 KB Output is correct
22 Correct 989 ms 4876 KB Output is correct
23 Correct 1147 ms 5096 KB Output is correct
24 Correct 1147 ms 5152 KB Output is correct
25 Correct 1105 ms 5180 KB Output is correct
26 Correct 25 ms 2124 KB Output is correct
27 Correct 476 ms 5100 KB Output is correct
28 Correct 496 ms 4920 KB Output is correct
29 Correct 973 ms 4232 KB Output is correct
30 Correct 928 ms 6256 KB Output is correct
31 Correct 722 ms 4292 KB Output is correct
32 Correct 287 ms 3664 KB Output is correct
33 Correct 708 ms 4328 KB Output is correct
34 Correct 716 ms 4292 KB Output is correct
35 Correct 25 ms 2132 KB Output is correct
36 Correct 703 ms 4312 KB Output is correct
37 Correct 656 ms 4308 KB Output is correct
38 Correct 634 ms 4300 KB Output is correct
39 Correct 595 ms 3680 KB Output is correct
40 Correct 579 ms 3400 KB Output is correct
41 Correct 611 ms 5304 KB Output is correct
42 Correct 570 ms 4920 KB Output is correct
43 Correct 1977 ms 5040 KB Output is correct
44 Correct 27 ms 3532 KB Output is correct
45 Correct 214 ms 4532 KB Output is correct
46 Correct 89 ms 4864 KB Output is correct
47 Correct 912 ms 7200 KB Output is correct
48 Correct 1974 ms 6804 KB Output is correct
49 Correct 894 ms 7300 KB Output is correct
50 Correct 887 ms 5008 KB Output is correct
51 Correct 887 ms 4984 KB Output is correct
52 Correct 922 ms 5384 KB Output is correct
53 Correct 1469 ms 5732 KB Output is correct
54 Correct 1402 ms 5668 KB Output is correct
55 Correct 1457 ms 6024 KB Output is correct
56 Correct 852 ms 7544 KB Output is correct
57 Correct 878 ms 7476 KB Output is correct
58 Correct 2013 ms 6324 KB Output is correct
59 Correct 2072 ms 6216 KB Output is correct
60 Correct 2032 ms 6404 KB Output is correct
61 Correct 1999 ms 6456 KB Output is correct
62 Correct 1688 ms 6340 KB Output is correct
63 Correct 1653 ms 6504 KB Output is correct
64 Correct 1916 ms 6404 KB Output is correct
65 Correct 1076 ms 6168 KB Output is correct
66 Correct 1036 ms 5008 KB Output is correct
67 Correct 1120 ms 5044 KB Output is correct
68 Correct 1074 ms 4936 KB Output is correct
69 Correct 988 ms 5000 KB Output is correct
70 Correct 1141 ms 5108 KB Output is correct
71 Correct 1151 ms 4788 KB Output is correct
72 Correct 1110 ms 4924 KB Output is correct
73 Correct 1108 ms 4864 KB Output is correct
74 Correct 1081 ms 4840 KB Output is correct
75 Correct 1069 ms 4856 KB Output is correct
76 Correct 982 ms 4964 KB Output is correct
77 Correct 965 ms 4868 KB Output is correct
78 Correct 968 ms 4816 KB Output is correct
79 Correct 919 ms 3760 KB Output is correct
80 Correct 944 ms 3956 KB Output is correct
81 Correct 926 ms 3784 KB Output is correct
82 Correct 910 ms 5244 KB Output is correct
83 Correct 900 ms 5216 KB Output is correct
84 Correct 889 ms 5364 KB Output is correct
85 Correct 2136 ms 7672 KB Output is correct
86 Correct 221 ms 5424 KB Output is correct
87 Correct 95 ms 5360 KB Output is correct
88 Correct 1061 ms 7780 KB Output is correct
89 Correct 2156 ms 7440 KB Output is correct
90 Correct 1085 ms 7876 KB Output is correct
91 Correct 1079 ms 6336 KB Output is correct
92 Correct 1114 ms 6324 KB Output is correct
93 Correct 1151 ms 6592 KB Output is correct
94 Correct 1666 ms 7076 KB Output is correct
95 Correct 1649 ms 7160 KB Output is correct
96 Correct 1659 ms 7384 KB Output is correct
97 Correct 972 ms 7524 KB Output is correct
98 Correct 1000 ms 8948 KB Output is correct
99 Correct 2177 ms 7484 KB Output is correct
100 Correct 2220 ms 7424 KB Output is correct
101 Correct 2192 ms 8556 KB Output is correct
102 Correct 2199 ms 8632 KB Output is correct
103 Correct 1885 ms 8544 KB Output is correct
104 Correct 1838 ms 8576 KB Output is correct
105 Correct 1750 ms 9816 KB Output is correct
106 Correct 1516 ms 9688 KB Output is correct
107 Correct 1712 ms 7680 KB Output is correct
108 Correct 2120 ms 8860 KB Output is correct
109 Correct 1221 ms 8104 KB Output is correct