# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
255876 |
2020-08-02T03:18:18 Z |
balbit |
Bridges (APIO19_bridges) |
C++14 |
|
2673 ms |
18424 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
const int maxn = 5e4+100;
//vector<pii> g[maxn];
struct ed{
int a,b,w;
};
int par[maxn], sz[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a==b)return;
sz[b] += sz[a];
par[a] = b;
}
struct ASK{
int s,w,i;
};
const int bs = 800;
vector<int> g[maxn];
ll re = 0;
bool seen[maxn];
void DFS(int v) {
bug(v);
seen[v] = 1;
re += sz[(v)];
for (int u : g[v]) {
if (!seen[u]) DFS(u);
}
}
signed main(){
IOS();
int n,m; cin>>n>>m;
vector<ed> v;
for (int i = 0; i<m; ++i) {
int a,b,w; cin>>a>>b>>w;
--a; --b;
v.pb({a,b,w});
}
int q; cin>>q;
vector<int> ans(q);
vector<int> tmp(m);
for (int i = 0; i<q; i+=bs) {
bug("HIIII");
vector<int> idk(m,0);
vector<int> dunno;
vector<pair<pii, int> > chgq; // list of {changes,i}
vector<ASK > ask;
for (int j = i; j<min(i+bs, q); ++j) {
int foo; cin>>foo;
if (foo == 1) {
int x,r; cin>>x>>r; --x;
chgq.pb({{x,r},j});
if (!idk[x]) dunno.pb(x);
idk[x] = 1;
}else{
int s,w; cin>>s>>w; --s;
ask.pb({s,w,j});
}
}
for (int j = 0; j<n; ++j) par[j] = j, sz[j] = 1;
vector<ed> V; V.reserve(m-SZ(dunno)+2);
for (int j = 0; j<m; ++j) if (!idk[j]) V.pb(v[j]);
sort(ALL(V),[&](ed a, ed b){return a.w > b.w;});
int vit = 0;
sort(ALL(ask), [&](ASK a, ASK b){return a.w > b.w;});
for (ASK &a : ask) {
while (vit < SZ(V) && V[vit].w >= a.w) {
// if (!idk[vit]) {
merge(V[vit].a, V[vit].b);
// }
++vit;
}
for (int x : dunno) tmp[x] = v[x].w;
for (auto & p:chgq) {
if (p.s > a.i) break;
tmp[p.f.f] = p.f.s;
}
vector<int> ps;
for (int x : dunno) {
if (tmp[x] >= a.w) {
int A = find(v[x].a), B = find(v[x].b);
if (A!=B){
g[A].pb(B);
g[B].pb(A);
ps.pb(A); ps.pb(B);
}
}
}
re = 0;
DFS(find(a.s));
ans[a.i] = re;
for (int x : ps) {
g[x].clear(); seen[x] = 0;
}
seen[find(a.s)] =0;
}
// sort(ALL(chgq), [&](pair<pii, int> a, pair<pii, int> b){return a.s < b.s;});
for (auto & p : chgq) {
v[p.f.f].w = p.f.s;
}
}
for (int i = 0; i<q; ++i) {
if (ans[i]) cout<<ans[i]<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1536 KB |
Output is correct |
2 |
Correct |
1 ms |
1536 KB |
Output is correct |
3 |
Correct |
30 ms |
1664 KB |
Output is correct |
4 |
Correct |
8 ms |
1664 KB |
Output is correct |
5 |
Correct |
23 ms |
1536 KB |
Output is correct |
6 |
Correct |
21 ms |
1656 KB |
Output is correct |
7 |
Correct |
25 ms |
1656 KB |
Output is correct |
8 |
Correct |
23 ms |
1664 KB |
Output is correct |
9 |
Correct |
30 ms |
1656 KB |
Output is correct |
10 |
Correct |
23 ms |
1536 KB |
Output is correct |
11 |
Correct |
23 ms |
1536 KB |
Output is correct |
12 |
Correct |
24 ms |
1536 KB |
Output is correct |
13 |
Correct |
31 ms |
1656 KB |
Output is correct |
14 |
Correct |
27 ms |
1656 KB |
Output is correct |
15 |
Correct |
24 ms |
1664 KB |
Output is correct |
16 |
Correct |
25 ms |
1656 KB |
Output is correct |
17 |
Correct |
26 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1633 ms |
5968 KB |
Output is correct |
2 |
Correct |
1651 ms |
5404 KB |
Output is correct |
3 |
Correct |
1690 ms |
5924 KB |
Output is correct |
4 |
Correct |
1618 ms |
5928 KB |
Output is correct |
5 |
Correct |
1618 ms |
5948 KB |
Output is correct |
6 |
Correct |
2405 ms |
5488 KB |
Output is correct |
7 |
Correct |
2298 ms |
5380 KB |
Output is correct |
8 |
Correct |
2246 ms |
5540 KB |
Output is correct |
9 |
Correct |
43 ms |
2176 KB |
Output is correct |
10 |
Correct |
1587 ms |
5412 KB |
Output is correct |
11 |
Correct |
1461 ms |
5388 KB |
Output is correct |
12 |
Correct |
1349 ms |
4832 KB |
Output is correct |
13 |
Correct |
1412 ms |
5804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1503 ms |
8692 KB |
Output is correct |
2 |
Correct |
1219 ms |
6356 KB |
Output is correct |
3 |
Correct |
1843 ms |
13172 KB |
Output is correct |
4 |
Correct |
1566 ms |
18424 KB |
Output is correct |
5 |
Correct |
41 ms |
2172 KB |
Output is correct |
6 |
Correct |
1804 ms |
15548 KB |
Output is correct |
7 |
Correct |
1498 ms |
14964 KB |
Output is correct |
8 |
Correct |
1308 ms |
11128 KB |
Output is correct |
9 |
Correct |
1059 ms |
7156 KB |
Output is correct |
10 |
Correct |
948 ms |
6132 KB |
Output is correct |
11 |
Correct |
1105 ms |
13588 KB |
Output is correct |
12 |
Correct |
995 ms |
10104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1967 ms |
5944 KB |
Output is correct |
2 |
Correct |
44 ms |
2168 KB |
Output is correct |
3 |
Correct |
180 ms |
4780 KB |
Output is correct |
4 |
Correct |
88 ms |
4716 KB |
Output is correct |
5 |
Correct |
1197 ms |
6068 KB |
Output is correct |
6 |
Correct |
1936 ms |
5960 KB |
Output is correct |
7 |
Correct |
1191 ms |
6104 KB |
Output is correct |
8 |
Correct |
887 ms |
4120 KB |
Output is correct |
9 |
Correct |
859 ms |
4128 KB |
Output is correct |
10 |
Correct |
873 ms |
4256 KB |
Output is correct |
11 |
Correct |
1374 ms |
5108 KB |
Output is correct |
12 |
Correct |
1356 ms |
5116 KB |
Output is correct |
13 |
Correct |
1367 ms |
5236 KB |
Output is correct |
14 |
Correct |
1134 ms |
6260 KB |
Output is correct |
15 |
Correct |
1163 ms |
6068 KB |
Output is correct |
16 |
Correct |
1915 ms |
5920 KB |
Output is correct |
17 |
Correct |
1940 ms |
5980 KB |
Output is correct |
18 |
Correct |
1869 ms |
5980 KB |
Output is correct |
19 |
Correct |
1924 ms |
5976 KB |
Output is correct |
20 |
Correct |
1591 ms |
5648 KB |
Output is correct |
21 |
Correct |
1610 ms |
5648 KB |
Output is correct |
22 |
Correct |
1939 ms |
5920 KB |
Output is correct |
23 |
Correct |
1082 ms |
5560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1633 ms |
5968 KB |
Output is correct |
2 |
Correct |
1651 ms |
5404 KB |
Output is correct |
3 |
Correct |
1690 ms |
5924 KB |
Output is correct |
4 |
Correct |
1618 ms |
5928 KB |
Output is correct |
5 |
Correct |
1618 ms |
5948 KB |
Output is correct |
6 |
Correct |
2405 ms |
5488 KB |
Output is correct |
7 |
Correct |
2298 ms |
5380 KB |
Output is correct |
8 |
Correct |
2246 ms |
5540 KB |
Output is correct |
9 |
Correct |
43 ms |
2176 KB |
Output is correct |
10 |
Correct |
1587 ms |
5412 KB |
Output is correct |
11 |
Correct |
1461 ms |
5388 KB |
Output is correct |
12 |
Correct |
1349 ms |
4832 KB |
Output is correct |
13 |
Correct |
1412 ms |
5804 KB |
Output is correct |
14 |
Correct |
1503 ms |
8692 KB |
Output is correct |
15 |
Correct |
1219 ms |
6356 KB |
Output is correct |
16 |
Correct |
1843 ms |
13172 KB |
Output is correct |
17 |
Correct |
1566 ms |
18424 KB |
Output is correct |
18 |
Correct |
41 ms |
2172 KB |
Output is correct |
19 |
Correct |
1804 ms |
15548 KB |
Output is correct |
20 |
Correct |
1498 ms |
14964 KB |
Output is correct |
21 |
Correct |
1308 ms |
11128 KB |
Output is correct |
22 |
Correct |
1059 ms |
7156 KB |
Output is correct |
23 |
Correct |
948 ms |
6132 KB |
Output is correct |
24 |
Correct |
1105 ms |
13588 KB |
Output is correct |
25 |
Correct |
995 ms |
10104 KB |
Output is correct |
26 |
Correct |
2019 ms |
11860 KB |
Output is correct |
27 |
Correct |
2218 ms |
8684 KB |
Output is correct |
28 |
Correct |
1930 ms |
14836 KB |
Output is correct |
29 |
Correct |
1422 ms |
8512 KB |
Output is correct |
30 |
Correct |
2110 ms |
6180 KB |
Output is correct |
31 |
Correct |
2156 ms |
6084 KB |
Output is correct |
32 |
Correct |
2145 ms |
5492 KB |
Output is correct |
33 |
Correct |
1826 ms |
6052 KB |
Output is correct |
34 |
Correct |
1835 ms |
6052 KB |
Output is correct |
35 |
Correct |
1884 ms |
6036 KB |
Output is correct |
36 |
Correct |
1416 ms |
5544 KB |
Output is correct |
37 |
Correct |
1402 ms |
5488 KB |
Output is correct |
38 |
Correct |
1392 ms |
6056 KB |
Output is correct |
39 |
Correct |
1081 ms |
4872 KB |
Output is correct |
40 |
Correct |
1103 ms |
4896 KB |
Output is correct |
41 |
Correct |
1079 ms |
4896 KB |
Output is correct |
42 |
Correct |
1125 ms |
5928 KB |
Output is correct |
43 |
Correct |
1090 ms |
5928 KB |
Output is correct |
44 |
Correct |
1067 ms |
5976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1536 KB |
Output is correct |
2 |
Correct |
1 ms |
1536 KB |
Output is correct |
3 |
Correct |
30 ms |
1664 KB |
Output is correct |
4 |
Correct |
8 ms |
1664 KB |
Output is correct |
5 |
Correct |
23 ms |
1536 KB |
Output is correct |
6 |
Correct |
21 ms |
1656 KB |
Output is correct |
7 |
Correct |
25 ms |
1656 KB |
Output is correct |
8 |
Correct |
23 ms |
1664 KB |
Output is correct |
9 |
Correct |
30 ms |
1656 KB |
Output is correct |
10 |
Correct |
23 ms |
1536 KB |
Output is correct |
11 |
Correct |
23 ms |
1536 KB |
Output is correct |
12 |
Correct |
24 ms |
1536 KB |
Output is correct |
13 |
Correct |
31 ms |
1656 KB |
Output is correct |
14 |
Correct |
27 ms |
1656 KB |
Output is correct |
15 |
Correct |
24 ms |
1664 KB |
Output is correct |
16 |
Correct |
25 ms |
1656 KB |
Output is correct |
17 |
Correct |
26 ms |
1536 KB |
Output is correct |
18 |
Correct |
1633 ms |
5968 KB |
Output is correct |
19 |
Correct |
1651 ms |
5404 KB |
Output is correct |
20 |
Correct |
1690 ms |
5924 KB |
Output is correct |
21 |
Correct |
1618 ms |
5928 KB |
Output is correct |
22 |
Correct |
1618 ms |
5948 KB |
Output is correct |
23 |
Correct |
2405 ms |
5488 KB |
Output is correct |
24 |
Correct |
2298 ms |
5380 KB |
Output is correct |
25 |
Correct |
2246 ms |
5540 KB |
Output is correct |
26 |
Correct |
43 ms |
2176 KB |
Output is correct |
27 |
Correct |
1587 ms |
5412 KB |
Output is correct |
28 |
Correct |
1461 ms |
5388 KB |
Output is correct |
29 |
Correct |
1349 ms |
4832 KB |
Output is correct |
30 |
Correct |
1412 ms |
5804 KB |
Output is correct |
31 |
Correct |
1503 ms |
8692 KB |
Output is correct |
32 |
Correct |
1219 ms |
6356 KB |
Output is correct |
33 |
Correct |
1843 ms |
13172 KB |
Output is correct |
34 |
Correct |
1566 ms |
18424 KB |
Output is correct |
35 |
Correct |
41 ms |
2172 KB |
Output is correct |
36 |
Correct |
1804 ms |
15548 KB |
Output is correct |
37 |
Correct |
1498 ms |
14964 KB |
Output is correct |
38 |
Correct |
1308 ms |
11128 KB |
Output is correct |
39 |
Correct |
1059 ms |
7156 KB |
Output is correct |
40 |
Correct |
948 ms |
6132 KB |
Output is correct |
41 |
Correct |
1105 ms |
13588 KB |
Output is correct |
42 |
Correct |
995 ms |
10104 KB |
Output is correct |
43 |
Correct |
1967 ms |
5944 KB |
Output is correct |
44 |
Correct |
44 ms |
2168 KB |
Output is correct |
45 |
Correct |
180 ms |
4780 KB |
Output is correct |
46 |
Correct |
88 ms |
4716 KB |
Output is correct |
47 |
Correct |
1197 ms |
6068 KB |
Output is correct |
48 |
Correct |
1936 ms |
5960 KB |
Output is correct |
49 |
Correct |
1191 ms |
6104 KB |
Output is correct |
50 |
Correct |
887 ms |
4120 KB |
Output is correct |
51 |
Correct |
859 ms |
4128 KB |
Output is correct |
52 |
Correct |
873 ms |
4256 KB |
Output is correct |
53 |
Correct |
1374 ms |
5108 KB |
Output is correct |
54 |
Correct |
1356 ms |
5116 KB |
Output is correct |
55 |
Correct |
1367 ms |
5236 KB |
Output is correct |
56 |
Correct |
1134 ms |
6260 KB |
Output is correct |
57 |
Correct |
1163 ms |
6068 KB |
Output is correct |
58 |
Correct |
1915 ms |
5920 KB |
Output is correct |
59 |
Correct |
1940 ms |
5980 KB |
Output is correct |
60 |
Correct |
1869 ms |
5980 KB |
Output is correct |
61 |
Correct |
1924 ms |
5976 KB |
Output is correct |
62 |
Correct |
1591 ms |
5648 KB |
Output is correct |
63 |
Correct |
1610 ms |
5648 KB |
Output is correct |
64 |
Correct |
1939 ms |
5920 KB |
Output is correct |
65 |
Correct |
1082 ms |
5560 KB |
Output is correct |
66 |
Correct |
2019 ms |
11860 KB |
Output is correct |
67 |
Correct |
2218 ms |
8684 KB |
Output is correct |
68 |
Correct |
1930 ms |
14836 KB |
Output is correct |
69 |
Correct |
1422 ms |
8512 KB |
Output is correct |
70 |
Correct |
2110 ms |
6180 KB |
Output is correct |
71 |
Correct |
2156 ms |
6084 KB |
Output is correct |
72 |
Correct |
2145 ms |
5492 KB |
Output is correct |
73 |
Correct |
1826 ms |
6052 KB |
Output is correct |
74 |
Correct |
1835 ms |
6052 KB |
Output is correct |
75 |
Correct |
1884 ms |
6036 KB |
Output is correct |
76 |
Correct |
1416 ms |
5544 KB |
Output is correct |
77 |
Correct |
1402 ms |
5488 KB |
Output is correct |
78 |
Correct |
1392 ms |
6056 KB |
Output is correct |
79 |
Correct |
1081 ms |
4872 KB |
Output is correct |
80 |
Correct |
1103 ms |
4896 KB |
Output is correct |
81 |
Correct |
1079 ms |
4896 KB |
Output is correct |
82 |
Correct |
1125 ms |
5928 KB |
Output is correct |
83 |
Correct |
1090 ms |
5928 KB |
Output is correct |
84 |
Correct |
1067 ms |
5976 KB |
Output is correct |
85 |
Correct |
2659 ms |
10624 KB |
Output is correct |
86 |
Correct |
214 ms |
6624 KB |
Output is correct |
87 |
Correct |
134 ms |
6752 KB |
Output is correct |
88 |
Correct |
1734 ms |
9288 KB |
Output is correct |
89 |
Correct |
2673 ms |
14420 KB |
Output is correct |
90 |
Correct |
1699 ms |
9304 KB |
Output is correct |
91 |
Correct |
1780 ms |
8784 KB |
Output is correct |
92 |
Correct |
1795 ms |
9000 KB |
Output is correct |
93 |
Correct |
2330 ms |
7408 KB |
Output is correct |
94 |
Correct |
1922 ms |
9844 KB |
Output is correct |
95 |
Correct |
1998 ms |
10076 KB |
Output is correct |
96 |
Correct |
1878 ms |
8144 KB |
Output is correct |
97 |
Correct |
1368 ms |
8656 KB |
Output is correct |
98 |
Correct |
1406 ms |
9056 KB |
Output is correct |
99 |
Correct |
2586 ms |
12136 KB |
Output is correct |
100 |
Correct |
2558 ms |
11924 KB |
Output is correct |
101 |
Correct |
2596 ms |
12084 KB |
Output is correct |
102 |
Correct |
2585 ms |
12012 KB |
Output is correct |
103 |
Correct |
2001 ms |
8516 KB |
Output is correct |
104 |
Correct |
2017 ms |
8520 KB |
Output is correct |
105 |
Correct |
1706 ms |
8476 KB |
Output is correct |
106 |
Correct |
1441 ms |
8000 KB |
Output is correct |
107 |
Correct |
1690 ms |
8908 KB |
Output is correct |
108 |
Correct |
2550 ms |
10508 KB |
Output is correct |
109 |
Correct |
1572 ms |
7492 KB |
Output is correct |