//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int block = 1000, M = 1e5, N = 5e4;
stack<tuple<int, int, int > > st;
int lab[N + 1], n, m, a[M + 1], b[M + 1], w[M + 1], t[M + 1], x[M + 1], y[M + 1], q, res[M + 1];
bitset<M + 1> changed;
vector<int> upt[M + 1];
int FindSet(int u)
{
return lab[u] < 0 ? u : FindSet(lab[u]);
}
void Unite(int u, int v)
{
u = FindSet(u);
v = FindSet(v);
if (u == v)
{
return ;
}
if (lab[u] > lab[v])
{
swap(u, v);
}
lab[u] += lab[v];
st.push(make_tuple(u, v, lab[v]));
lab[v] = u;
}
void roll_back(int sz)
{
while(st.size() > sz)
{
int u, v, s;
tie(u, v, s) = st.top();
st.pop();
lab[u] -= s;
lab[v] = s;
}
}
void read()
{
cin >> n >> m;
for (int i = 1; i <= m; ++ i)
{
cin >> a[i] >> b[i] >> w[i];
}
cin >> q;
for (int i = 1; i <= q; ++ i)
{
cin >> t[i] >> x[i] >> y[i];
}
}
void solve()
{
for (int l = 1; l <= q; l+= block)
{
int r = min(q, l + block - 1);
changed.reset();
memset(lab, -1, sizeof(lab));
while(!st.empty())
{
st.pop();
}
vector<int> tmp, query;
for (int i = l; i <= r; ++ i)
{
if (t[i] == 1)
{
changed[x[i]] = true;
tmp.push_back(x[i]);
}
}
vector<int> unchanged;
for (int i = 1; i <= m; ++ i)
{
if (!changed[i])
{
unchanged.push_back(i);
}
}
sort(unchanged.begin(), unchanged.end(), [&](const int &a, const int &b)
{
return w[a] < w[b];
});
for (int i = l; i <= r; ++ i)
{
if (t[i] == 1)
{
w[x[i]] = y[i];
//tmp.push_back(i);
}
else
{
for (int j : tmp)
{
if (w[j] >= y[i])
{
upt[i].push_back(j);
}
}
query.push_back(i);
}
}
sort(query.begin(), query.end(), [&](const int & a, const int &b)
{
return y[a] > y[b];
});
for (int i : query)
{
//cerr << i << '\n';
while(!unchanged.empty() && w[unchanged.back()] >= y[i])
{
//cerr << unchanged.back() << ' ';
Unite(a[unchanged.back()], b[unchanged.back()]);
unchanged.pop_back();
}
//cerr << '\n';
int sz = st.size();
for (int j : upt[i])
{
Unite(a[j], b[j]);
//cerr << j << ' ';
}
//cerr << '\n';
res[i] = -lab[FindSet(x[i])];
roll_back(sz);
//cerr << '\n';
}
}
for (int i = 1; i <= q; ++ i)
{
if (t[i] == 1)
{
continue;
}
cout << res[i] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | while(st.size() > sz)
| ~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2900 KB |
Output is correct |
2 |
Correct |
2 ms |
2808 KB |
Output is correct |
3 |
Correct |
41 ms |
9820 KB |
Output is correct |
4 |
Correct |
6 ms |
3284 KB |
Output is correct |
5 |
Correct |
44 ms |
10596 KB |
Output is correct |
6 |
Correct |
34 ms |
10812 KB |
Output is correct |
7 |
Correct |
38 ms |
10744 KB |
Output is correct |
8 |
Correct |
40 ms |
9188 KB |
Output is correct |
9 |
Correct |
57 ms |
15096 KB |
Output is correct |
10 |
Correct |
41 ms |
9992 KB |
Output is correct |
11 |
Correct |
42 ms |
9844 KB |
Output is correct |
12 |
Correct |
50 ms |
12288 KB |
Output is correct |
13 |
Correct |
48 ms |
10404 KB |
Output is correct |
14 |
Correct |
43 ms |
9672 KB |
Output is correct |
15 |
Correct |
48 ms |
10408 KB |
Output is correct |
16 |
Correct |
48 ms |
13264 KB |
Output is correct |
17 |
Correct |
46 ms |
12464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1195 ms |
73280 KB |
Output is correct |
2 |
Correct |
1210 ms |
73240 KB |
Output is correct |
3 |
Correct |
1234 ms |
73528 KB |
Output is correct |
4 |
Correct |
1292 ms |
73012 KB |
Output is correct |
5 |
Correct |
1249 ms |
73740 KB |
Output is correct |
6 |
Correct |
1812 ms |
131304 KB |
Output is correct |
7 |
Correct |
1812 ms |
127968 KB |
Output is correct |
8 |
Correct |
1802 ms |
127604 KB |
Output is correct |
9 |
Correct |
35 ms |
4784 KB |
Output is correct |
10 |
Correct |
1024 ms |
98676 KB |
Output is correct |
11 |
Correct |
952 ms |
98144 KB |
Output is correct |
12 |
Correct |
1049 ms |
53320 KB |
Output is correct |
13 |
Correct |
1039 ms |
46316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
967 ms |
73260 KB |
Output is correct |
2 |
Correct |
802 ms |
98292 KB |
Output is correct |
3 |
Correct |
1210 ms |
101392 KB |
Output is correct |
4 |
Correct |
974 ms |
72628 KB |
Output is correct |
5 |
Correct |
34 ms |
4828 KB |
Output is correct |
6 |
Correct |
1130 ms |
92616 KB |
Output is correct |
7 |
Correct |
891 ms |
64716 KB |
Output is correct |
8 |
Correct |
755 ms |
48864 KB |
Output is correct |
9 |
Correct |
652 ms |
40576 KB |
Output is correct |
10 |
Correct |
583 ms |
29132 KB |
Output is correct |
11 |
Correct |
662 ms |
38220 KB |
Output is correct |
12 |
Correct |
591 ms |
27732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1389 ms |
7276 KB |
Output is correct |
2 |
Correct |
37 ms |
5964 KB |
Output is correct |
3 |
Correct |
147 ms |
6956 KB |
Output is correct |
4 |
Correct |
70 ms |
7064 KB |
Output is correct |
5 |
Correct |
683 ms |
9408 KB |
Output is correct |
6 |
Correct |
1338 ms |
11252 KB |
Output is correct |
7 |
Correct |
698 ms |
9388 KB |
Output is correct |
8 |
Correct |
645 ms |
8672 KB |
Output is correct |
9 |
Correct |
658 ms |
8908 KB |
Output is correct |
10 |
Correct |
657 ms |
8796 KB |
Output is correct |
11 |
Correct |
1038 ms |
9668 KB |
Output is correct |
12 |
Correct |
1006 ms |
9956 KB |
Output is correct |
13 |
Correct |
1020 ms |
9672 KB |
Output is correct |
14 |
Correct |
611 ms |
9388 KB |
Output is correct |
15 |
Correct |
680 ms |
9368 KB |
Output is correct |
16 |
Correct |
1372 ms |
10724 KB |
Output is correct |
17 |
Correct |
1381 ms |
10884 KB |
Output is correct |
18 |
Correct |
1364 ms |
10888 KB |
Output is correct |
19 |
Correct |
1344 ms |
11048 KB |
Output is correct |
20 |
Correct |
1148 ms |
10076 KB |
Output is correct |
21 |
Correct |
1137 ms |
10192 KB |
Output is correct |
22 |
Correct |
1304 ms |
10836 KB |
Output is correct |
23 |
Correct |
747 ms |
9256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1195 ms |
73280 KB |
Output is correct |
2 |
Correct |
1210 ms |
73240 KB |
Output is correct |
3 |
Correct |
1234 ms |
73528 KB |
Output is correct |
4 |
Correct |
1292 ms |
73012 KB |
Output is correct |
5 |
Correct |
1249 ms |
73740 KB |
Output is correct |
6 |
Correct |
1812 ms |
131304 KB |
Output is correct |
7 |
Correct |
1812 ms |
127968 KB |
Output is correct |
8 |
Correct |
1802 ms |
127604 KB |
Output is correct |
9 |
Correct |
35 ms |
4784 KB |
Output is correct |
10 |
Correct |
1024 ms |
98676 KB |
Output is correct |
11 |
Correct |
952 ms |
98144 KB |
Output is correct |
12 |
Correct |
1049 ms |
53320 KB |
Output is correct |
13 |
Correct |
1039 ms |
46316 KB |
Output is correct |
14 |
Correct |
967 ms |
73260 KB |
Output is correct |
15 |
Correct |
802 ms |
98292 KB |
Output is correct |
16 |
Correct |
1210 ms |
101392 KB |
Output is correct |
17 |
Correct |
974 ms |
72628 KB |
Output is correct |
18 |
Correct |
34 ms |
4828 KB |
Output is correct |
19 |
Correct |
1130 ms |
92616 KB |
Output is correct |
20 |
Correct |
891 ms |
64716 KB |
Output is correct |
21 |
Correct |
755 ms |
48864 KB |
Output is correct |
22 |
Correct |
652 ms |
40576 KB |
Output is correct |
23 |
Correct |
583 ms |
29132 KB |
Output is correct |
24 |
Correct |
662 ms |
38220 KB |
Output is correct |
25 |
Correct |
591 ms |
27732 KB |
Output is correct |
26 |
Correct |
1187 ms |
73328 KB |
Output is correct |
27 |
Correct |
1522 ms |
102620 KB |
Output is correct |
28 |
Correct |
1261 ms |
71532 KB |
Output is correct |
29 |
Correct |
867 ms |
28548 KB |
Output is correct |
30 |
Correct |
1431 ms |
88880 KB |
Output is correct |
31 |
Correct |
1448 ms |
91284 KB |
Output is correct |
32 |
Correct |
1468 ms |
92008 KB |
Output is correct |
33 |
Correct |
1218 ms |
71788 KB |
Output is correct |
34 |
Correct |
1221 ms |
71904 KB |
Output is correct |
35 |
Correct |
1237 ms |
72616 KB |
Output is correct |
36 |
Correct |
930 ms |
35680 KB |
Output is correct |
37 |
Correct |
915 ms |
34404 KB |
Output is correct |
38 |
Correct |
910 ms |
32636 KB |
Output is correct |
39 |
Correct |
757 ms |
18816 KB |
Output is correct |
40 |
Correct |
748 ms |
18036 KB |
Output is correct |
41 |
Correct |
755 ms |
17408 KB |
Output is correct |
42 |
Correct |
727 ms |
17092 KB |
Output is correct |
43 |
Correct |
724 ms |
16576 KB |
Output is correct |
44 |
Correct |
730 ms |
16004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2900 KB |
Output is correct |
2 |
Correct |
2 ms |
2808 KB |
Output is correct |
3 |
Correct |
41 ms |
9820 KB |
Output is correct |
4 |
Correct |
6 ms |
3284 KB |
Output is correct |
5 |
Correct |
44 ms |
10596 KB |
Output is correct |
6 |
Correct |
34 ms |
10812 KB |
Output is correct |
7 |
Correct |
38 ms |
10744 KB |
Output is correct |
8 |
Correct |
40 ms |
9188 KB |
Output is correct |
9 |
Correct |
57 ms |
15096 KB |
Output is correct |
10 |
Correct |
41 ms |
9992 KB |
Output is correct |
11 |
Correct |
42 ms |
9844 KB |
Output is correct |
12 |
Correct |
50 ms |
12288 KB |
Output is correct |
13 |
Correct |
48 ms |
10404 KB |
Output is correct |
14 |
Correct |
43 ms |
9672 KB |
Output is correct |
15 |
Correct |
48 ms |
10408 KB |
Output is correct |
16 |
Correct |
48 ms |
13264 KB |
Output is correct |
17 |
Correct |
46 ms |
12464 KB |
Output is correct |
18 |
Correct |
1195 ms |
73280 KB |
Output is correct |
19 |
Correct |
1210 ms |
73240 KB |
Output is correct |
20 |
Correct |
1234 ms |
73528 KB |
Output is correct |
21 |
Correct |
1292 ms |
73012 KB |
Output is correct |
22 |
Correct |
1249 ms |
73740 KB |
Output is correct |
23 |
Correct |
1812 ms |
131304 KB |
Output is correct |
24 |
Correct |
1812 ms |
127968 KB |
Output is correct |
25 |
Correct |
1802 ms |
127604 KB |
Output is correct |
26 |
Correct |
35 ms |
4784 KB |
Output is correct |
27 |
Correct |
1024 ms |
98676 KB |
Output is correct |
28 |
Correct |
952 ms |
98144 KB |
Output is correct |
29 |
Correct |
1049 ms |
53320 KB |
Output is correct |
30 |
Correct |
1039 ms |
46316 KB |
Output is correct |
31 |
Correct |
967 ms |
73260 KB |
Output is correct |
32 |
Correct |
802 ms |
98292 KB |
Output is correct |
33 |
Correct |
1210 ms |
101392 KB |
Output is correct |
34 |
Correct |
974 ms |
72628 KB |
Output is correct |
35 |
Correct |
34 ms |
4828 KB |
Output is correct |
36 |
Correct |
1130 ms |
92616 KB |
Output is correct |
37 |
Correct |
891 ms |
64716 KB |
Output is correct |
38 |
Correct |
755 ms |
48864 KB |
Output is correct |
39 |
Correct |
652 ms |
40576 KB |
Output is correct |
40 |
Correct |
583 ms |
29132 KB |
Output is correct |
41 |
Correct |
662 ms |
38220 KB |
Output is correct |
42 |
Correct |
591 ms |
27732 KB |
Output is correct |
43 |
Correct |
1389 ms |
7276 KB |
Output is correct |
44 |
Correct |
37 ms |
5964 KB |
Output is correct |
45 |
Correct |
147 ms |
6956 KB |
Output is correct |
46 |
Correct |
70 ms |
7064 KB |
Output is correct |
47 |
Correct |
683 ms |
9408 KB |
Output is correct |
48 |
Correct |
1338 ms |
11252 KB |
Output is correct |
49 |
Correct |
698 ms |
9388 KB |
Output is correct |
50 |
Correct |
645 ms |
8672 KB |
Output is correct |
51 |
Correct |
658 ms |
8908 KB |
Output is correct |
52 |
Correct |
657 ms |
8796 KB |
Output is correct |
53 |
Correct |
1038 ms |
9668 KB |
Output is correct |
54 |
Correct |
1006 ms |
9956 KB |
Output is correct |
55 |
Correct |
1020 ms |
9672 KB |
Output is correct |
56 |
Correct |
611 ms |
9388 KB |
Output is correct |
57 |
Correct |
680 ms |
9368 KB |
Output is correct |
58 |
Correct |
1372 ms |
10724 KB |
Output is correct |
59 |
Correct |
1381 ms |
10884 KB |
Output is correct |
60 |
Correct |
1364 ms |
10888 KB |
Output is correct |
61 |
Correct |
1344 ms |
11048 KB |
Output is correct |
62 |
Correct |
1148 ms |
10076 KB |
Output is correct |
63 |
Correct |
1137 ms |
10192 KB |
Output is correct |
64 |
Correct |
1304 ms |
10836 KB |
Output is correct |
65 |
Correct |
747 ms |
9256 KB |
Output is correct |
66 |
Correct |
1187 ms |
73328 KB |
Output is correct |
67 |
Correct |
1522 ms |
102620 KB |
Output is correct |
68 |
Correct |
1261 ms |
71532 KB |
Output is correct |
69 |
Correct |
867 ms |
28548 KB |
Output is correct |
70 |
Correct |
1431 ms |
88880 KB |
Output is correct |
71 |
Correct |
1448 ms |
91284 KB |
Output is correct |
72 |
Correct |
1468 ms |
92008 KB |
Output is correct |
73 |
Correct |
1218 ms |
71788 KB |
Output is correct |
74 |
Correct |
1221 ms |
71904 KB |
Output is correct |
75 |
Correct |
1237 ms |
72616 KB |
Output is correct |
76 |
Correct |
930 ms |
35680 KB |
Output is correct |
77 |
Correct |
915 ms |
34404 KB |
Output is correct |
78 |
Correct |
910 ms |
32636 KB |
Output is correct |
79 |
Correct |
757 ms |
18816 KB |
Output is correct |
80 |
Correct |
748 ms |
18036 KB |
Output is correct |
81 |
Correct |
755 ms |
17408 KB |
Output is correct |
82 |
Correct |
727 ms |
17092 KB |
Output is correct |
83 |
Correct |
724 ms |
16576 KB |
Output is correct |
84 |
Correct |
730 ms |
16004 KB |
Output is correct |
85 |
Correct |
1842 ms |
78052 KB |
Output is correct |
86 |
Correct |
183 ms |
13148 KB |
Output is correct |
87 |
Correct |
128 ms |
17532 KB |
Output is correct |
88 |
Correct |
1123 ms |
89944 KB |
Output is correct |
89 |
Correct |
1838 ms |
76392 KB |
Output is correct |
90 |
Correct |
1143 ms |
98156 KB |
Output is correct |
91 |
Correct |
1265 ms |
75636 KB |
Output is correct |
92 |
Correct |
1276 ms |
75496 KB |
Output is correct |
93 |
Correct |
1851 ms |
113512 KB |
Output is correct |
94 |
Correct |
1556 ms |
76884 KB |
Output is correct |
95 |
Correct |
1540 ms |
76824 KB |
Output is correct |
96 |
Correct |
1904 ms |
117748 KB |
Output is correct |
97 |
Correct |
819 ms |
42564 KB |
Output is correct |
98 |
Correct |
883 ms |
39124 KB |
Output is correct |
99 |
Correct |
1878 ms |
78824 KB |
Output is correct |
100 |
Correct |
1894 ms |
77496 KB |
Output is correct |
101 |
Correct |
1908 ms |
77620 KB |
Output is correct |
102 |
Correct |
1881 ms |
77796 KB |
Output is correct |
103 |
Correct |
2127 ms |
122816 KB |
Output is correct |
104 |
Correct |
2107 ms |
122280 KB |
Output is correct |
105 |
Correct |
1607 ms |
50008 KB |
Output is correct |
106 |
Correct |
1186 ms |
30192 KB |
Output is correct |
107 |
Correct |
1442 ms |
57108 KB |
Output is correct |
108 |
Correct |
2001 ms |
113044 KB |
Output is correct |
109 |
Correct |
1554 ms |
116352 KB |
Output is correct |