#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#else
#define er(args ...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 1e5 + 5, sq = 400, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
int par[maxn], cnt[maxn];
int get(int x){
return par[x] == -1? x: par[x] = get(par[x]);
}
void unite(int u, int v){
u = get(u), v = get(v);
if(u - v){
cnt[u] += cnt[v];
par[v] = u;
}
}
int n, m;
vector<int> adj[maxn];
bool vis[maxn];
int dfs(int r){
vis[r] = true;
int res = cnt[r];
for(int c: adj[r]) if(!vis[c]) res += dfs(c);
return res;
}
int u[maxn], v[maxn], cr[maxn];
vector<pp> edge;
bool is_edge[maxn], use[maxn];
void slv(vector<pair<int, pp>> query){
fill(par, par + n, -1), fill(cnt, cnt + n, 1), fill(is_edge, is_edge + m, false);
vector<pair<pp, int>> srt;
vector<int> id_edge;
rep(i,0,sz(query)){
auto[t, p] = query[i];
auto[x, w] = p;
if(t == 1){
is_edge[x] = true;
id_edge.pb(x);
}else{
srt.pb({{w, x}, i});
}
}
int t = 0;
// reverse(all(query));
// rep(i,0,m) if(is_edge[i]) query.pb({1, {i, cr[i]}}), t++;
// reverse(all(query));
// for(auto&c: srt) c.ss += t;
sort(all(srt));
vector<int> tmp(sz(query), -1);
int ptr = m-1;
per(i,sz(srt)-1,0){
auto[w, x] = srt[i].ff;
while(ptr + 1 && edge[ptr].ff >= w){
if(!is_edge[edge[ptr].ss]){
unite(u[edge[ptr].ss], v[edge[ptr].ss]);
}
ptr--;
}
int id = srt[i].ss;
// er(i, w, x, id);
vector<int> seen;
per(j,id-1,0){
auto[t, p] = query[j];
auto[xx, ww] = p;
if(t == 1){
seen.pb(xx);
if(ww >= w && !use[xx]){
adj[get(u[xx])].pb(get(v[xx]));
adj[get(v[xx])].pb(get(u[xx]));
}
use[xx] = true;
}
}
for(int xx: id_edge){
seen.pb(xx);
if(!use[xx] && cr[xx] >= w){
adj[get(u[xx])].pb(get(v[xx]));
adj[get(v[xx])].pb(get(u[xx]));
}
use[xx] = true;
}
tmp[id] = dfs(get(x));
vis[get(x)] = false;
for(int c: seen) use[c] = false, adj[get(u[c])].clear(), adj[get(v[c])].clear(), vis[get(u[c])] = vis[get(v[c])] = false;
}
vector<pp> nw, nw2;
for(auto[w, id]: edge){
if(!is_edge[id]) nw.pb({w, id});
}
per(i,sz(query)-1,0){
auto[t, p] = query[i];
auto[x, w] = p;
if(t == 1){
if(!use[x]){
nw2.pb({w, x});
cr[x] = w;
}
use[x] = true;
}
}
for(auto[w, x]: nw2) use[x] = false;
sort(all(nw2));
edge.clear();
merge(all(nw), all(nw2), back_inserter(edge));
for(int c: tmp) if(c + 1) cout << c << '\n';
}
int main(){ IOS();
cin >> n >> m;
rep(i,0,m){
int w; cin >> u[i] >> v[i] >> w; u[i]--, v[i]--;
edge.pb({w, i});
cr[i] = w;
}
sort(all(edge));
int q; cin >> q;
vector<pair<int, pp>> query;
rep(i,1,q+1){
int t, x, w; cin >> t >> x >> w; x--;
query.pb({t, {x, w}});
if(i%sq == 0){
slv(query);
query.clear();
}
}
if(sz(query)){
slv(query);
query.clear();
}
return 0-0;
}
Compilation message
bridges.cpp: In function 'void slv(std::vector<std::pair<int, std::pair<int, int> > >)':
bridges.cpp:65:10: warning: unused variable 't' [-Wunused-variable]
65 | int t = 0;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
67 ms |
2796 KB |
Output is correct |
4 |
Correct |
23 ms |
2644 KB |
Output is correct |
5 |
Correct |
55 ms |
2744 KB |
Output is correct |
6 |
Correct |
53 ms |
2740 KB |
Output is correct |
7 |
Correct |
52 ms |
2748 KB |
Output is correct |
8 |
Correct |
47 ms |
2744 KB |
Output is correct |
9 |
Correct |
57 ms |
2736 KB |
Output is correct |
10 |
Correct |
48 ms |
2724 KB |
Output is correct |
11 |
Correct |
47 ms |
2644 KB |
Output is correct |
12 |
Correct |
51 ms |
2740 KB |
Output is correct |
13 |
Correct |
55 ms |
2752 KB |
Output is correct |
14 |
Correct |
52 ms |
2736 KB |
Output is correct |
15 |
Correct |
55 ms |
2756 KB |
Output is correct |
16 |
Correct |
53 ms |
2748 KB |
Output is correct |
17 |
Correct |
50 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1431 ms |
6576 KB |
Output is correct |
2 |
Correct |
1390 ms |
6564 KB |
Output is correct |
3 |
Correct |
1401 ms |
6668 KB |
Output is correct |
4 |
Correct |
1414 ms |
6652 KB |
Output is correct |
5 |
Correct |
1410 ms |
6612 KB |
Output is correct |
6 |
Correct |
1719 ms |
6416 KB |
Output is correct |
7 |
Correct |
1627 ms |
6436 KB |
Output is correct |
8 |
Correct |
1637 ms |
6440 KB |
Output is correct |
9 |
Correct |
197 ms |
2892 KB |
Output is correct |
10 |
Correct |
1380 ms |
6524 KB |
Output is correct |
11 |
Correct |
1334 ms |
6552 KB |
Output is correct |
12 |
Correct |
1031 ms |
6072 KB |
Output is correct |
13 |
Correct |
968 ms |
6500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1119 ms |
5356 KB |
Output is correct |
2 |
Correct |
798 ms |
3556 KB |
Output is correct |
3 |
Correct |
1249 ms |
5376 KB |
Output is correct |
4 |
Correct |
1148 ms |
5524 KB |
Output is correct |
5 |
Correct |
196 ms |
2884 KB |
Output is correct |
6 |
Correct |
1220 ms |
5364 KB |
Output is correct |
7 |
Correct |
1131 ms |
5212 KB |
Output is correct |
8 |
Correct |
1068 ms |
5216 KB |
Output is correct |
9 |
Correct |
795 ms |
4872 KB |
Output is correct |
10 |
Correct |
754 ms |
4772 KB |
Output is correct |
11 |
Correct |
708 ms |
5376 KB |
Output is correct |
12 |
Correct |
649 ms |
5248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2097 ms |
7632 KB |
Output is correct |
2 |
Correct |
193 ms |
2816 KB |
Output is correct |
3 |
Correct |
138 ms |
6676 KB |
Output is correct |
4 |
Correct |
112 ms |
6632 KB |
Output is correct |
5 |
Correct |
1644 ms |
7536 KB |
Output is correct |
6 |
Correct |
2060 ms |
7728 KB |
Output is correct |
7 |
Correct |
1657 ms |
7516 KB |
Output is correct |
8 |
Correct |
800 ms |
5312 KB |
Output is correct |
9 |
Correct |
804 ms |
5532 KB |
Output is correct |
10 |
Correct |
807 ms |
5664 KB |
Output is correct |
11 |
Correct |
1348 ms |
6916 KB |
Output is correct |
12 |
Correct |
1328 ms |
6700 KB |
Output is correct |
13 |
Correct |
1346 ms |
7048 KB |
Output is correct |
14 |
Correct |
1642 ms |
7592 KB |
Output is correct |
15 |
Correct |
1659 ms |
7752 KB |
Output is correct |
16 |
Correct |
2028 ms |
7712 KB |
Output is correct |
17 |
Correct |
2033 ms |
7528 KB |
Output is correct |
18 |
Correct |
1914 ms |
7544 KB |
Output is correct |
19 |
Correct |
1907 ms |
7468 KB |
Output is correct |
20 |
Correct |
1527 ms |
7188 KB |
Output is correct |
21 |
Correct |
1542 ms |
7232 KB |
Output is correct |
22 |
Correct |
1945 ms |
7524 KB |
Output is correct |
23 |
Correct |
1509 ms |
7256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1431 ms |
6576 KB |
Output is correct |
2 |
Correct |
1390 ms |
6564 KB |
Output is correct |
3 |
Correct |
1401 ms |
6668 KB |
Output is correct |
4 |
Correct |
1414 ms |
6652 KB |
Output is correct |
5 |
Correct |
1410 ms |
6612 KB |
Output is correct |
6 |
Correct |
1719 ms |
6416 KB |
Output is correct |
7 |
Correct |
1627 ms |
6436 KB |
Output is correct |
8 |
Correct |
1637 ms |
6440 KB |
Output is correct |
9 |
Correct |
197 ms |
2892 KB |
Output is correct |
10 |
Correct |
1380 ms |
6524 KB |
Output is correct |
11 |
Correct |
1334 ms |
6552 KB |
Output is correct |
12 |
Correct |
1031 ms |
6072 KB |
Output is correct |
13 |
Correct |
968 ms |
6500 KB |
Output is correct |
14 |
Correct |
1119 ms |
5356 KB |
Output is correct |
15 |
Correct |
798 ms |
3556 KB |
Output is correct |
16 |
Correct |
1249 ms |
5376 KB |
Output is correct |
17 |
Correct |
1148 ms |
5524 KB |
Output is correct |
18 |
Correct |
196 ms |
2884 KB |
Output is correct |
19 |
Correct |
1220 ms |
5364 KB |
Output is correct |
20 |
Correct |
1131 ms |
5212 KB |
Output is correct |
21 |
Correct |
1068 ms |
5216 KB |
Output is correct |
22 |
Correct |
795 ms |
4872 KB |
Output is correct |
23 |
Correct |
754 ms |
4772 KB |
Output is correct |
24 |
Correct |
708 ms |
5376 KB |
Output is correct |
25 |
Correct |
649 ms |
5248 KB |
Output is correct |
26 |
Correct |
1386 ms |
6548 KB |
Output is correct |
27 |
Correct |
1915 ms |
8184 KB |
Output is correct |
28 |
Correct |
1799 ms |
11020 KB |
Output is correct |
29 |
Correct |
1516 ms |
8092 KB |
Output is correct |
30 |
Correct |
1790 ms |
6648 KB |
Output is correct |
31 |
Correct |
1827 ms |
6756 KB |
Output is correct |
32 |
Correct |
1860 ms |
6660 KB |
Output is correct |
33 |
Correct |
1596 ms |
6600 KB |
Output is correct |
34 |
Correct |
1662 ms |
6592 KB |
Output is correct |
35 |
Correct |
1685 ms |
6668 KB |
Output is correct |
36 |
Correct |
1407 ms |
6620 KB |
Output is correct |
37 |
Correct |
1420 ms |
6580 KB |
Output is correct |
38 |
Correct |
1410 ms |
6680 KB |
Output is correct |
39 |
Correct |
1057 ms |
6048 KB |
Output is correct |
40 |
Correct |
1076 ms |
6040 KB |
Output is correct |
41 |
Correct |
1058 ms |
6156 KB |
Output is correct |
42 |
Correct |
888 ms |
6656 KB |
Output is correct |
43 |
Correct |
909 ms |
6656 KB |
Output is correct |
44 |
Correct |
897 ms |
6592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
67 ms |
2796 KB |
Output is correct |
4 |
Correct |
23 ms |
2644 KB |
Output is correct |
5 |
Correct |
55 ms |
2744 KB |
Output is correct |
6 |
Correct |
53 ms |
2740 KB |
Output is correct |
7 |
Correct |
52 ms |
2748 KB |
Output is correct |
8 |
Correct |
47 ms |
2744 KB |
Output is correct |
9 |
Correct |
57 ms |
2736 KB |
Output is correct |
10 |
Correct |
48 ms |
2724 KB |
Output is correct |
11 |
Correct |
47 ms |
2644 KB |
Output is correct |
12 |
Correct |
51 ms |
2740 KB |
Output is correct |
13 |
Correct |
55 ms |
2752 KB |
Output is correct |
14 |
Correct |
52 ms |
2736 KB |
Output is correct |
15 |
Correct |
55 ms |
2756 KB |
Output is correct |
16 |
Correct |
53 ms |
2748 KB |
Output is correct |
17 |
Correct |
50 ms |
2644 KB |
Output is correct |
18 |
Correct |
1431 ms |
6576 KB |
Output is correct |
19 |
Correct |
1390 ms |
6564 KB |
Output is correct |
20 |
Correct |
1401 ms |
6668 KB |
Output is correct |
21 |
Correct |
1414 ms |
6652 KB |
Output is correct |
22 |
Correct |
1410 ms |
6612 KB |
Output is correct |
23 |
Correct |
1719 ms |
6416 KB |
Output is correct |
24 |
Correct |
1627 ms |
6436 KB |
Output is correct |
25 |
Correct |
1637 ms |
6440 KB |
Output is correct |
26 |
Correct |
197 ms |
2892 KB |
Output is correct |
27 |
Correct |
1380 ms |
6524 KB |
Output is correct |
28 |
Correct |
1334 ms |
6552 KB |
Output is correct |
29 |
Correct |
1031 ms |
6072 KB |
Output is correct |
30 |
Correct |
968 ms |
6500 KB |
Output is correct |
31 |
Correct |
1119 ms |
5356 KB |
Output is correct |
32 |
Correct |
798 ms |
3556 KB |
Output is correct |
33 |
Correct |
1249 ms |
5376 KB |
Output is correct |
34 |
Correct |
1148 ms |
5524 KB |
Output is correct |
35 |
Correct |
196 ms |
2884 KB |
Output is correct |
36 |
Correct |
1220 ms |
5364 KB |
Output is correct |
37 |
Correct |
1131 ms |
5212 KB |
Output is correct |
38 |
Correct |
1068 ms |
5216 KB |
Output is correct |
39 |
Correct |
795 ms |
4872 KB |
Output is correct |
40 |
Correct |
754 ms |
4772 KB |
Output is correct |
41 |
Correct |
708 ms |
5376 KB |
Output is correct |
42 |
Correct |
649 ms |
5248 KB |
Output is correct |
43 |
Correct |
2097 ms |
7632 KB |
Output is correct |
44 |
Correct |
193 ms |
2816 KB |
Output is correct |
45 |
Correct |
138 ms |
6676 KB |
Output is correct |
46 |
Correct |
112 ms |
6632 KB |
Output is correct |
47 |
Correct |
1644 ms |
7536 KB |
Output is correct |
48 |
Correct |
2060 ms |
7728 KB |
Output is correct |
49 |
Correct |
1657 ms |
7516 KB |
Output is correct |
50 |
Correct |
800 ms |
5312 KB |
Output is correct |
51 |
Correct |
804 ms |
5532 KB |
Output is correct |
52 |
Correct |
807 ms |
5664 KB |
Output is correct |
53 |
Correct |
1348 ms |
6916 KB |
Output is correct |
54 |
Correct |
1328 ms |
6700 KB |
Output is correct |
55 |
Correct |
1346 ms |
7048 KB |
Output is correct |
56 |
Correct |
1642 ms |
7592 KB |
Output is correct |
57 |
Correct |
1659 ms |
7752 KB |
Output is correct |
58 |
Correct |
2028 ms |
7712 KB |
Output is correct |
59 |
Correct |
2033 ms |
7528 KB |
Output is correct |
60 |
Correct |
1914 ms |
7544 KB |
Output is correct |
61 |
Correct |
1907 ms |
7468 KB |
Output is correct |
62 |
Correct |
1527 ms |
7188 KB |
Output is correct |
63 |
Correct |
1542 ms |
7232 KB |
Output is correct |
64 |
Correct |
1945 ms |
7524 KB |
Output is correct |
65 |
Correct |
1509 ms |
7256 KB |
Output is correct |
66 |
Correct |
1386 ms |
6548 KB |
Output is correct |
67 |
Correct |
1915 ms |
8184 KB |
Output is correct |
68 |
Correct |
1799 ms |
11020 KB |
Output is correct |
69 |
Correct |
1516 ms |
8092 KB |
Output is correct |
70 |
Correct |
1790 ms |
6648 KB |
Output is correct |
71 |
Correct |
1827 ms |
6756 KB |
Output is correct |
72 |
Correct |
1860 ms |
6660 KB |
Output is correct |
73 |
Correct |
1596 ms |
6600 KB |
Output is correct |
74 |
Correct |
1662 ms |
6592 KB |
Output is correct |
75 |
Correct |
1685 ms |
6668 KB |
Output is correct |
76 |
Correct |
1407 ms |
6620 KB |
Output is correct |
77 |
Correct |
1420 ms |
6580 KB |
Output is correct |
78 |
Correct |
1410 ms |
6680 KB |
Output is correct |
79 |
Correct |
1057 ms |
6048 KB |
Output is correct |
80 |
Correct |
1076 ms |
6040 KB |
Output is correct |
81 |
Correct |
1058 ms |
6156 KB |
Output is correct |
82 |
Correct |
888 ms |
6656 KB |
Output is correct |
83 |
Correct |
909 ms |
6656 KB |
Output is correct |
84 |
Correct |
897 ms |
6592 KB |
Output is correct |
85 |
Correct |
2931 ms |
17084 KB |
Output is correct |
86 |
Correct |
206 ms |
8744 KB |
Output is correct |
87 |
Correct |
181 ms |
8680 KB |
Output is correct |
88 |
Correct |
2361 ms |
10680 KB |
Output is correct |
89 |
Correct |
2885 ms |
20664 KB |
Output is correct |
90 |
Correct |
2385 ms |
10208 KB |
Output is correct |
91 |
Correct |
1543 ms |
9332 KB |
Output is correct |
92 |
Correct |
1518 ms |
9420 KB |
Output is correct |
93 |
Correct |
1768 ms |
8460 KB |
Output is correct |
94 |
Correct |
2109 ms |
11256 KB |
Output is correct |
95 |
Correct |
2098 ms |
11776 KB |
Output is correct |
96 |
Correct |
2192 ms |
10268 KB |
Output is correct |
97 |
Correct |
1891 ms |
10084 KB |
Output is correct |
98 |
Correct |
1863 ms |
10232 KB |
Output is correct |
99 |
Correct |
2838 ms |
20000 KB |
Output is correct |
100 |
Correct |
2828 ms |
19960 KB |
Output is correct |
101 |
Correct |
2711 ms |
17700 KB |
Output is correct |
102 |
Correct |
2725 ms |
17848 KB |
Output is correct |
103 |
Correct |
2329 ms |
10572 KB |
Output is correct |
104 |
Correct |
2311 ms |
10364 KB |
Output is correct |
105 |
Correct |
1741 ms |
10440 KB |
Output is correct |
106 |
Correct |
1399 ms |
10208 KB |
Output is correct |
107 |
Correct |
1788 ms |
10572 KB |
Output is correct |
108 |
Correct |
2804 ms |
16296 KB |
Output is correct |
109 |
Correct |
2237 ms |
9016 KB |
Output is correct |