#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
void debug_out()
{
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
cerr << ' ' << A;
debug_out(B...);
}
#ifdef DEBUG
#define time(...) 42
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
mt19937 rng(time(0));
const int INF32 = 1e9 + 1337 + 228 + 1488;
const int BUBEN = 500;
const int maxV = 50004;
const int maxE = 100005;
const int maxQ = 100005;
int eV[maxE], eU[maxE], eF[maxE];
int qT[maxQ], qI[maxE], qF[maxE];
namespace dsu
{
int q[maxV];
vector< pair<int&, int> > stk;
void init()
{
memset(q, 255, sizeof(q));
stk.clear();
}
int gt(int a)
{
return q[a] < 0 ? a : gt(q[a]);
}
void un(int a, int b, bool memorize = false)
{
a = gt(a);
b = gt(b);
if (a == b) return;
if (-q[a] > -q[b])
swap(a, b);
if (memorize)
{
stk.emplace_back(q[a], q[a]);
stk.emplace_back(q[b], q[b]);
}
q[b] += q[a];
q[a] = b;
}
void backtrack()
{
while (!stk.empty())
{
stk.back().fi = stk.back().se;
stk.pop_back();
}
}
}
int ans[maxQ];
int e_ord[maxE];
int ge[maxE];
int be[maxE];
bool changes[maxE];
int mem_link[maxQ];
int mem[2 * BUBEN][2 * BUBEN];
signed main()
{
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; ++i)
{
cin >> eV[i] >> eU[i] >> eF[i];
}
iota(e_ord, e_ord + M, 1);
sort(e_ord, e_ord + M, [&](int e1, int e2) -> bool
{
return eF[e1] > eF[e2];
});
int Q;
cin >> Q;
for (int t = 1; t <= Q; ++t)
{
cin >> qT[t] >> qI[t] >> qF[t];
}
for (int t1 = 1; t1 <= Q; t1 += BUBEN)
{
// cout << ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
int t2 = min(Q, t1 + BUBEN - 1);
for (int t = t1; t <= t2; ++t)
{
if (qT[t] == 1)
{
int e = qI[t];
changes[e] = true;
}
}
int ge_cnt = 0;
int be_cnt = 0;
for (int i = 0; i < M; ++i)
{
int e = e_ord[i];
if (!changes[e])
{
ge[ge_cnt++] = e;
}
else
{
be[be_cnt++] = e;
}
}
/*cout << "ge: "; for (int i = 0; i < ge_cnt; ++i) cout << ge[i] << ' '; cout << endl;
cout << " "; for (int i = 0; i < ge_cnt; ++i) cout << eF[ge[i]] << ' '; cout << endl;
cout << "be: "; for (int i = 0; i < be_cnt; ++i) cout << be[i] << ' '; cout << endl;
cout << " "; for (int i = 0; i < be_cnt; ++i) cout << eF[be[i]] << ' '; cout << endl;/**/
int mem_ptr = 0;
vector<int> ask;
for (int t = t1; t <= t2; ++t)
{
if (qT[t] == 1)
{
int e = qI[t];
eF[e] = qF[t];
}
else
{
int v = qI[t];
mem_link[t] = mem_ptr++;
for (int i = 0; i < be_cnt; ++i)
{
mem[mem_link[t]][i] = eF[be[i]];
}
ask.push_back(t);
}
}
sort(all(ask), [&](int t1, int t2) -> bool
{
return qF[t1] > qF[t2];
});
dsu::init();
int ge_ptr = 0;
for (int ai = 0; ai < ask.size(); ++ai)
{
int t = ask[ai];
while (ge_ptr < ge_cnt && eF[ge[ge_ptr]] >= qF[t])
{
int e = ge[ge_ptr++];
dsu::un(eV[e], eU[e]);
}
for (int bi = 0; bi < be_cnt; ++bi)
{
int e = be[bi];
int f = mem[mem_link[t]][bi];
if (f >= qF[t])
{
dsu::un(eV[e], eU[e], true);
}
}
ans[t] = -dsu::q[dsu::gt(qI[t])];
dsu::backtrack();
}
sort(be, be + be_cnt, [&](int e1, int e2) -> bool
{
return eF[e1] > eF[e2];
});
int ptr1 = 0, ptr2 = 0;
for (int i = 0; i < M; ++i)
{
if (ptr2 < be_cnt && (ptr1 >= ge_cnt || eF[ge[ptr1]] < eF[be[ptr2]]))
{
e_ord[i] = be[ptr2++];
}
else
{
e_ord[i] = ge[ptr1++];
}
}
for (int t = t1; t <= t2; ++t)
{
if (qT[t] == 1)
{
changes[qI[t]] = false;
}
}
}
for (int t = 1; t <= Q; ++t)
if (qT[t] == 2)
cout << ans[t] << '\n';
return 0;
}
Compilation message
bridges.cpp:154:97: warning: "/*" within comment [-Wcomment]
cout << " "; for (int i = 0; i < be_cnt; ++i) cout << eF[be[i]] << ' '; cout << endl;/**/
bridges.cpp: In function 'int main()':
bridges.cpp:167:21: warning: unused variable 'v' [-Wunused-variable]
int v = qI[t];
^
bridges.cpp:182:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ai = 0; ai < ask.size(); ++ai)
~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
21 ms |
2048 KB |
Output is correct |
4 |
Correct |
9 ms |
896 KB |
Output is correct |
5 |
Correct |
14 ms |
2048 KB |
Output is correct |
6 |
Correct |
12 ms |
2048 KB |
Output is correct |
7 |
Correct |
15 ms |
1920 KB |
Output is correct |
8 |
Correct |
16 ms |
2048 KB |
Output is correct |
9 |
Correct |
18 ms |
1920 KB |
Output is correct |
10 |
Correct |
16 ms |
2048 KB |
Output is correct |
11 |
Correct |
16 ms |
2048 KB |
Output is correct |
12 |
Correct |
18 ms |
2048 KB |
Output is correct |
13 |
Correct |
19 ms |
2176 KB |
Output is correct |
14 |
Correct |
18 ms |
2048 KB |
Output is correct |
15 |
Correct |
17 ms |
2080 KB |
Output is correct |
16 |
Correct |
16 ms |
2048 KB |
Output is correct |
17 |
Correct |
16 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
705 ms |
5496 KB |
Output is correct |
2 |
Correct |
694 ms |
5368 KB |
Output is correct |
3 |
Correct |
684 ms |
5368 KB |
Output is correct |
4 |
Correct |
721 ms |
5224 KB |
Output is correct |
5 |
Correct |
706 ms |
5496 KB |
Output is correct |
6 |
Correct |
1018 ms |
5472 KB |
Output is correct |
7 |
Correct |
1004 ms |
5624 KB |
Output is correct |
8 |
Correct |
1002 ms |
5472 KB |
Output is correct |
9 |
Correct |
47 ms |
3192 KB |
Output is correct |
10 |
Correct |
726 ms |
5368 KB |
Output is correct |
11 |
Correct |
687 ms |
5500 KB |
Output is correct |
12 |
Correct |
581 ms |
6396 KB |
Output is correct |
13 |
Correct |
619 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
593 ms |
4984 KB |
Output is correct |
2 |
Correct |
442 ms |
4476 KB |
Output is correct |
3 |
Correct |
676 ms |
4960 KB |
Output is correct |
4 |
Correct |
580 ms |
4856 KB |
Output is correct |
5 |
Correct |
43 ms |
3068 KB |
Output is correct |
6 |
Correct |
633 ms |
4984 KB |
Output is correct |
7 |
Correct |
516 ms |
4856 KB |
Output is correct |
8 |
Correct |
461 ms |
4988 KB |
Output is correct |
9 |
Correct |
394 ms |
5752 KB |
Output is correct |
10 |
Correct |
368 ms |
5752 KB |
Output is correct |
11 |
Correct |
407 ms |
3960 KB |
Output is correct |
12 |
Correct |
366 ms |
3960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1020 ms |
5860 KB |
Output is correct |
2 |
Correct |
44 ms |
3576 KB |
Output is correct |
3 |
Correct |
115 ms |
3576 KB |
Output is correct |
4 |
Correct |
91 ms |
3576 KB |
Output is correct |
5 |
Correct |
764 ms |
5752 KB |
Output is correct |
6 |
Correct |
956 ms |
6040 KB |
Output is correct |
7 |
Correct |
774 ms |
5856 KB |
Output is correct |
8 |
Correct |
440 ms |
4620 KB |
Output is correct |
9 |
Correct |
433 ms |
4564 KB |
Output is correct |
10 |
Correct |
432 ms |
4728 KB |
Output is correct |
11 |
Correct |
747 ms |
5112 KB |
Output is correct |
12 |
Correct |
717 ms |
5176 KB |
Output is correct |
13 |
Correct |
751 ms |
5368 KB |
Output is correct |
14 |
Correct |
767 ms |
5976 KB |
Output is correct |
15 |
Correct |
756 ms |
5940 KB |
Output is correct |
16 |
Correct |
1018 ms |
6136 KB |
Output is correct |
17 |
Correct |
1034 ms |
5928 KB |
Output is correct |
18 |
Correct |
1029 ms |
6008 KB |
Output is correct |
19 |
Correct |
1008 ms |
6092 KB |
Output is correct |
20 |
Correct |
859 ms |
5496 KB |
Output is correct |
21 |
Correct |
869 ms |
5880 KB |
Output is correct |
22 |
Correct |
998 ms |
6136 KB |
Output is correct |
23 |
Correct |
796 ms |
5628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
705 ms |
5496 KB |
Output is correct |
2 |
Correct |
694 ms |
5368 KB |
Output is correct |
3 |
Correct |
684 ms |
5368 KB |
Output is correct |
4 |
Correct |
721 ms |
5224 KB |
Output is correct |
5 |
Correct |
706 ms |
5496 KB |
Output is correct |
6 |
Correct |
1018 ms |
5472 KB |
Output is correct |
7 |
Correct |
1004 ms |
5624 KB |
Output is correct |
8 |
Correct |
1002 ms |
5472 KB |
Output is correct |
9 |
Correct |
47 ms |
3192 KB |
Output is correct |
10 |
Correct |
726 ms |
5368 KB |
Output is correct |
11 |
Correct |
687 ms |
5500 KB |
Output is correct |
12 |
Correct |
581 ms |
6396 KB |
Output is correct |
13 |
Correct |
619 ms |
4216 KB |
Output is correct |
14 |
Correct |
593 ms |
4984 KB |
Output is correct |
15 |
Correct |
442 ms |
4476 KB |
Output is correct |
16 |
Correct |
676 ms |
4960 KB |
Output is correct |
17 |
Correct |
580 ms |
4856 KB |
Output is correct |
18 |
Correct |
43 ms |
3068 KB |
Output is correct |
19 |
Correct |
633 ms |
4984 KB |
Output is correct |
20 |
Correct |
516 ms |
4856 KB |
Output is correct |
21 |
Correct |
461 ms |
4988 KB |
Output is correct |
22 |
Correct |
394 ms |
5752 KB |
Output is correct |
23 |
Correct |
368 ms |
5752 KB |
Output is correct |
24 |
Correct |
407 ms |
3960 KB |
Output is correct |
25 |
Correct |
366 ms |
3960 KB |
Output is correct |
26 |
Correct |
788 ms |
5240 KB |
Output is correct |
27 |
Correct |
929 ms |
5368 KB |
Output is correct |
28 |
Correct |
781 ms |
5224 KB |
Output is correct |
29 |
Correct |
585 ms |
5368 KB |
Output is correct |
30 |
Correct |
848 ms |
5240 KB |
Output is correct |
31 |
Correct |
875 ms |
5240 KB |
Output is correct |
32 |
Correct |
877 ms |
5240 KB |
Output is correct |
33 |
Correct |
751 ms |
5316 KB |
Output is correct |
34 |
Correct |
754 ms |
5196 KB |
Output is correct |
35 |
Correct |
765 ms |
5244 KB |
Output is correct |
36 |
Correct |
586 ms |
5148 KB |
Output is correct |
37 |
Correct |
596 ms |
5112 KB |
Output is correct |
38 |
Correct |
592 ms |
5112 KB |
Output is correct |
39 |
Correct |
495 ms |
6008 KB |
Output is correct |
40 |
Correct |
506 ms |
6008 KB |
Output is correct |
41 |
Correct |
499 ms |
6008 KB |
Output is correct |
42 |
Correct |
470 ms |
4280 KB |
Output is correct |
43 |
Correct |
469 ms |
4344 KB |
Output is correct |
44 |
Correct |
462 ms |
4320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
640 KB |
Output is correct |
3 |
Correct |
21 ms |
2048 KB |
Output is correct |
4 |
Correct |
9 ms |
896 KB |
Output is correct |
5 |
Correct |
14 ms |
2048 KB |
Output is correct |
6 |
Correct |
12 ms |
2048 KB |
Output is correct |
7 |
Correct |
15 ms |
1920 KB |
Output is correct |
8 |
Correct |
16 ms |
2048 KB |
Output is correct |
9 |
Correct |
18 ms |
1920 KB |
Output is correct |
10 |
Correct |
16 ms |
2048 KB |
Output is correct |
11 |
Correct |
16 ms |
2048 KB |
Output is correct |
12 |
Correct |
18 ms |
2048 KB |
Output is correct |
13 |
Correct |
19 ms |
2176 KB |
Output is correct |
14 |
Correct |
18 ms |
2048 KB |
Output is correct |
15 |
Correct |
17 ms |
2080 KB |
Output is correct |
16 |
Correct |
16 ms |
2048 KB |
Output is correct |
17 |
Correct |
16 ms |
2048 KB |
Output is correct |
18 |
Correct |
705 ms |
5496 KB |
Output is correct |
19 |
Correct |
694 ms |
5368 KB |
Output is correct |
20 |
Correct |
684 ms |
5368 KB |
Output is correct |
21 |
Correct |
721 ms |
5224 KB |
Output is correct |
22 |
Correct |
706 ms |
5496 KB |
Output is correct |
23 |
Correct |
1018 ms |
5472 KB |
Output is correct |
24 |
Correct |
1004 ms |
5624 KB |
Output is correct |
25 |
Correct |
1002 ms |
5472 KB |
Output is correct |
26 |
Correct |
47 ms |
3192 KB |
Output is correct |
27 |
Correct |
726 ms |
5368 KB |
Output is correct |
28 |
Correct |
687 ms |
5500 KB |
Output is correct |
29 |
Correct |
581 ms |
6396 KB |
Output is correct |
30 |
Correct |
619 ms |
4216 KB |
Output is correct |
31 |
Correct |
593 ms |
4984 KB |
Output is correct |
32 |
Correct |
442 ms |
4476 KB |
Output is correct |
33 |
Correct |
676 ms |
4960 KB |
Output is correct |
34 |
Correct |
580 ms |
4856 KB |
Output is correct |
35 |
Correct |
43 ms |
3068 KB |
Output is correct |
36 |
Correct |
633 ms |
4984 KB |
Output is correct |
37 |
Correct |
516 ms |
4856 KB |
Output is correct |
38 |
Correct |
461 ms |
4988 KB |
Output is correct |
39 |
Correct |
394 ms |
5752 KB |
Output is correct |
40 |
Correct |
368 ms |
5752 KB |
Output is correct |
41 |
Correct |
407 ms |
3960 KB |
Output is correct |
42 |
Correct |
366 ms |
3960 KB |
Output is correct |
43 |
Correct |
1020 ms |
5860 KB |
Output is correct |
44 |
Correct |
44 ms |
3576 KB |
Output is correct |
45 |
Correct |
115 ms |
3576 KB |
Output is correct |
46 |
Correct |
91 ms |
3576 KB |
Output is correct |
47 |
Correct |
764 ms |
5752 KB |
Output is correct |
48 |
Correct |
956 ms |
6040 KB |
Output is correct |
49 |
Correct |
774 ms |
5856 KB |
Output is correct |
50 |
Correct |
440 ms |
4620 KB |
Output is correct |
51 |
Correct |
433 ms |
4564 KB |
Output is correct |
52 |
Correct |
432 ms |
4728 KB |
Output is correct |
53 |
Correct |
747 ms |
5112 KB |
Output is correct |
54 |
Correct |
717 ms |
5176 KB |
Output is correct |
55 |
Correct |
751 ms |
5368 KB |
Output is correct |
56 |
Correct |
767 ms |
5976 KB |
Output is correct |
57 |
Correct |
756 ms |
5940 KB |
Output is correct |
58 |
Correct |
1018 ms |
6136 KB |
Output is correct |
59 |
Correct |
1034 ms |
5928 KB |
Output is correct |
60 |
Correct |
1029 ms |
6008 KB |
Output is correct |
61 |
Correct |
1008 ms |
6092 KB |
Output is correct |
62 |
Correct |
859 ms |
5496 KB |
Output is correct |
63 |
Correct |
869 ms |
5880 KB |
Output is correct |
64 |
Correct |
998 ms |
6136 KB |
Output is correct |
65 |
Correct |
796 ms |
5628 KB |
Output is correct |
66 |
Correct |
788 ms |
5240 KB |
Output is correct |
67 |
Correct |
929 ms |
5368 KB |
Output is correct |
68 |
Correct |
781 ms |
5224 KB |
Output is correct |
69 |
Correct |
585 ms |
5368 KB |
Output is correct |
70 |
Correct |
848 ms |
5240 KB |
Output is correct |
71 |
Correct |
875 ms |
5240 KB |
Output is correct |
72 |
Correct |
877 ms |
5240 KB |
Output is correct |
73 |
Correct |
751 ms |
5316 KB |
Output is correct |
74 |
Correct |
754 ms |
5196 KB |
Output is correct |
75 |
Correct |
765 ms |
5244 KB |
Output is correct |
76 |
Correct |
586 ms |
5148 KB |
Output is correct |
77 |
Correct |
596 ms |
5112 KB |
Output is correct |
78 |
Correct |
592 ms |
5112 KB |
Output is correct |
79 |
Correct |
495 ms |
6008 KB |
Output is correct |
80 |
Correct |
506 ms |
6008 KB |
Output is correct |
81 |
Correct |
499 ms |
6008 KB |
Output is correct |
82 |
Correct |
470 ms |
4280 KB |
Output is correct |
83 |
Correct |
469 ms |
4344 KB |
Output is correct |
84 |
Correct |
462 ms |
4320 KB |
Output is correct |
85 |
Correct |
1243 ms |
9864 KB |
Output is correct |
86 |
Correct |
137 ms |
5844 KB |
Output is correct |
87 |
Correct |
109 ms |
5880 KB |
Output is correct |
88 |
Correct |
1029 ms |
8312 KB |
Output is correct |
89 |
Correct |
1236 ms |
10072 KB |
Output is correct |
90 |
Correct |
1047 ms |
8268 KB |
Output is correct |
91 |
Correct |
757 ms |
7440 KB |
Output is correct |
92 |
Correct |
760 ms |
7672 KB |
Output is correct |
93 |
Correct |
1078 ms |
7728 KB |
Output is correct |
94 |
Correct |
1052 ms |
8572 KB |
Output is correct |
95 |
Correct |
1020 ms |
8628 KB |
Output is correct |
96 |
Correct |
1139 ms |
8612 KB |
Output is correct |
97 |
Correct |
888 ms |
9036 KB |
Output is correct |
98 |
Correct |
942 ms |
7416 KB |
Output is correct |
99 |
Correct |
1285 ms |
9708 KB |
Output is correct |
100 |
Correct |
1355 ms |
9748 KB |
Output is correct |
101 |
Correct |
1347 ms |
9720 KB |
Output is correct |
102 |
Correct |
1290 ms |
9848 KB |
Output is correct |
103 |
Correct |
1278 ms |
8952 KB |
Output is correct |
104 |
Correct |
1276 ms |
8952 KB |
Output is correct |
105 |
Correct |
1051 ms |
7936 KB |
Output is correct |
106 |
Correct |
895 ms |
7568 KB |
Output is correct |
107 |
Correct |
976 ms |
9952 KB |
Output is correct |
108 |
Correct |
1291 ms |
9384 KB |
Output is correct |
109 |
Correct |
1115 ms |
7692 KB |
Output is correct |