#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef tuple<int, int, int, int, int> edge; // weight, startTime, endTime, endpts (x2)
typedef tuple<int, int, int> query; // weight, time, pt
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const int BLKSZ = 400;
const int NUMBLKS = 100000 / BLKSZ + 5;
const int MAXN = 50100;
struct DSU {
int anc[MAXN], sz[MAXN], rank[MAXN];
void init() {
for (int i = 0; i < MAXN; i++) {
anc[i] = i;
sz[i] = 1;
rank[i] = 0;
}
}
int fRt(int i) {
return anc[i] == i ? i : anc[i] = fRt(anc[i]);
}
bool merge(int a, int b) { // TODO: implement rank
a = fRt(a), b = fRt(b);
if (a == b) {
return false;
}
if (rank[a] < rank[b]) {
anc[a] = b;
sz[b] += sz[a];
} else if (rank[a] > rank[b]) {
anc[b] = a;
sz[a] += sz[b];
}
else{
anc[b] = a;
sz[a] += sz[b];
rank[a]++;
}
return true;
}
} ds;
vector<vi> aList;
vector<bool> vis;
vector<int> undo;
int cnt = 0;
void dfs(int cV) {
vis[cV] = true;
cnt += ds.sz[cV];
for (int aV : aList[cV]) {
if (!vis[aV]) {
dfs(aV);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("bridges.in", "r", stdin);
int V, E, Q;
cin >> V >> E;
vector<edge> edges;
vector<pi> endP(E);
vi sT(E);
vi lW(E);
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
endP[i] = {u, v};
sT[i] = -1;
lW[i] = w;
}
cin >> Q;
vector<vector<query>> qBlks(NUMBLKS);
vector<vector<edge>> eBlks(NUMBLKS);
for (int cT = 0; cT < Q; cT++) {
int t, x, w;
cin >> t >> x >> w;
x--;
if (t == 1) {
edge cE = {lW[x], sT[x], cT - 1, endP[x].f, endP[x].s};
edges.pb(cE);
eBlks[sT[x] / BLKSZ].pb(cE);
eBlks[(cT - 1) / BLKSZ].pb(cE);
sT[x] = cT;
lW[x] = w;
} else {
qBlks[cT / BLKSZ].pb({w, cT, x});
}
}
for (int x = 0; x < E; x++) {
edge cE = {lW[x], sT[x], 100005, endP[x].f, endP[x].s};
edges.pb(cE);
eBlks[sT[x] / BLKSZ].pb(cE);
eBlks[100005 / BLKSZ].pb(cE);
}
edges.pb({-1, -1, -1, -1, -1}); // dummy edge with weight -1 to make sure all queries are processed
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
// decreasing weight
aList.resize(V);
vis.resize(V, false);
vi qAns(Q, -1);
for (int cBlk = 0; cBlk < NUMBLKS; cBlk++) {
vector<query> &cQs = qBlks[cBlk];
vector<edge> &cEs = eBlks[cBlk];
sort(cQs.begin(), cQs.end());
reverse(cQs.begin(), cQs.end());
// decreasing weight
int blkL = cBlk * BLKSZ;
int blkR = (cBlk + 1) * BLKSZ - 1;
ds.init();
int nxtQ = 0;
for (edge oE: edges) {
int oW = get<0>(oE);
int oST = get<1>(oE);
int oET = get<2>(oE);
int oU = get<3>(oE);
int oV = get<4>(oE);
while (nxtQ < cQs.size() && get<0>(cQs[nxtQ]) > oW) {
int qW = get<0>(cQs[nxtQ]);
int qT = get<1>(cQs[nxtQ]);
int qPt = get<2>(cQs[nxtQ]);
// we have components determined by ds and a set of extra edges
for (edge iE : cEs) {
int iW = get<0>(iE);
int iST = get<1>(iE);
int iET = get<2>(iE);
int iU = ds.fRt(get<3>(iE));
int iV = ds.fRt(get<4>(iE));
if (iU == iV) { // useless
continue;
}
if (iST <= qT && qT <= iET && iW >= qW) { // usable iff within time zone and qW
aList[iU].pb(iV);
aList[iV].pb(iU);
undo.pb(iU);
undo.pb(iV);
}
}
dfs(ds.fRt(qPt));
undo.pb(ds.fRt(qPt));
qAns[qT] = cnt;
for (int cV : undo) {
aList[cV].clear();
vis[cV] = false;
}
undo.clear();
cnt = 0;
nxtQ++;
}
// only consider edges that completely surround this block
if (oST < blkL && blkR < oET) {
// merge endpoints in disjoint set
ds.merge(oU, oV);
}
}
}
for (int i = 0; i < Q; i++) {
if (qAns[i] != -1) {
cout << qAns[i] << '\n';
}
}
cout << flush;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nxtQ < cQs.size() && get<0>(cQs[nxtQ]) > oW) {
~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
1016 KB |
Output is correct |
2 |
Correct |
29 ms |
1016 KB |
Output is correct |
3 |
Correct |
59 ms |
1656 KB |
Output is correct |
4 |
Correct |
33 ms |
1272 KB |
Output is correct |
5 |
Correct |
99 ms |
1640 KB |
Output is correct |
6 |
Correct |
59 ms |
1528 KB |
Output is correct |
7 |
Correct |
64 ms |
1588 KB |
Output is correct |
8 |
Correct |
60 ms |
1656 KB |
Output is correct |
9 |
Correct |
70 ms |
1528 KB |
Output is correct |
10 |
Correct |
60 ms |
1528 KB |
Output is correct |
11 |
Correct |
62 ms |
1528 KB |
Output is correct |
12 |
Correct |
68 ms |
1532 KB |
Output is correct |
13 |
Correct |
68 ms |
1644 KB |
Output is correct |
14 |
Correct |
64 ms |
1528 KB |
Output is correct |
15 |
Correct |
66 ms |
1604 KB |
Output is correct |
16 |
Correct |
62 ms |
1548 KB |
Output is correct |
17 |
Correct |
61 ms |
1528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1508 ms |
12196 KB |
Output is correct |
2 |
Correct |
1482 ms |
12136 KB |
Output is correct |
3 |
Correct |
1487 ms |
12184 KB |
Output is correct |
4 |
Correct |
1439 ms |
12060 KB |
Output is correct |
5 |
Correct |
1456 ms |
12184 KB |
Output is correct |
6 |
Correct |
1705 ms |
12056 KB |
Output is correct |
7 |
Correct |
1612 ms |
12008 KB |
Output is correct |
8 |
Correct |
1571 ms |
12056 KB |
Output is correct |
9 |
Correct |
72 ms |
3192 KB |
Output is correct |
10 |
Correct |
1377 ms |
12204 KB |
Output is correct |
11 |
Correct |
1323 ms |
12200 KB |
Output is correct |
12 |
Correct |
976 ms |
9336 KB |
Output is correct |
13 |
Correct |
1324 ms |
13912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1178 ms |
10100 KB |
Output is correct |
2 |
Correct |
739 ms |
7144 KB |
Output is correct |
3 |
Correct |
1174 ms |
10240 KB |
Output is correct |
4 |
Correct |
1121 ms |
10136 KB |
Output is correct |
5 |
Correct |
72 ms |
3196 KB |
Output is correct |
6 |
Correct |
1128 ms |
10008 KB |
Output is correct |
7 |
Correct |
1049 ms |
10012 KB |
Output is correct |
8 |
Correct |
996 ms |
9880 KB |
Output is correct |
9 |
Correct |
706 ms |
7712 KB |
Output is correct |
10 |
Correct |
686 ms |
7600 KB |
Output is correct |
11 |
Correct |
954 ms |
12244 KB |
Output is correct |
12 |
Correct |
929 ms |
12376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1502 ms |
12220 KB |
Output is correct |
2 |
Correct |
74 ms |
3448 KB |
Output is correct |
3 |
Correct |
618 ms |
9040 KB |
Output is correct |
4 |
Correct |
629 ms |
9192 KB |
Output is correct |
5 |
Correct |
1426 ms |
12460 KB |
Output is correct |
6 |
Correct |
1505 ms |
12276 KB |
Output is correct |
7 |
Correct |
1441 ms |
12272 KB |
Output is correct |
8 |
Correct |
1035 ms |
8276 KB |
Output is correct |
9 |
Correct |
1068 ms |
8300 KB |
Output is correct |
10 |
Correct |
951 ms |
8468 KB |
Output is correct |
11 |
Correct |
1543 ms |
10424 KB |
Output is correct |
12 |
Correct |
1509 ms |
10224 KB |
Output is correct |
13 |
Correct |
1348 ms |
10476 KB |
Output is correct |
14 |
Correct |
1302 ms |
12496 KB |
Output is correct |
15 |
Correct |
1394 ms |
12528 KB |
Output is correct |
16 |
Correct |
1661 ms |
12140 KB |
Output is correct |
17 |
Correct |
1685 ms |
12272 KB |
Output is correct |
18 |
Correct |
1715 ms |
12268 KB |
Output is correct |
19 |
Correct |
1721 ms |
12180 KB |
Output is correct |
20 |
Correct |
1485 ms |
11240 KB |
Output is correct |
21 |
Correct |
1450 ms |
11244 KB |
Output is correct |
22 |
Correct |
1480 ms |
12144 KB |
Output is correct |
23 |
Correct |
1243 ms |
10784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1508 ms |
12196 KB |
Output is correct |
2 |
Correct |
1482 ms |
12136 KB |
Output is correct |
3 |
Correct |
1487 ms |
12184 KB |
Output is correct |
4 |
Correct |
1439 ms |
12060 KB |
Output is correct |
5 |
Correct |
1456 ms |
12184 KB |
Output is correct |
6 |
Correct |
1705 ms |
12056 KB |
Output is correct |
7 |
Correct |
1612 ms |
12008 KB |
Output is correct |
8 |
Correct |
1571 ms |
12056 KB |
Output is correct |
9 |
Correct |
72 ms |
3192 KB |
Output is correct |
10 |
Correct |
1377 ms |
12204 KB |
Output is correct |
11 |
Correct |
1323 ms |
12200 KB |
Output is correct |
12 |
Correct |
976 ms |
9336 KB |
Output is correct |
13 |
Correct |
1324 ms |
13912 KB |
Output is correct |
14 |
Correct |
1178 ms |
10100 KB |
Output is correct |
15 |
Correct |
739 ms |
7144 KB |
Output is correct |
16 |
Correct |
1174 ms |
10240 KB |
Output is correct |
17 |
Correct |
1121 ms |
10136 KB |
Output is correct |
18 |
Correct |
72 ms |
3196 KB |
Output is correct |
19 |
Correct |
1128 ms |
10008 KB |
Output is correct |
20 |
Correct |
1049 ms |
10012 KB |
Output is correct |
21 |
Correct |
996 ms |
9880 KB |
Output is correct |
22 |
Correct |
706 ms |
7712 KB |
Output is correct |
23 |
Correct |
686 ms |
7600 KB |
Output is correct |
24 |
Correct |
954 ms |
12244 KB |
Output is correct |
25 |
Correct |
929 ms |
12376 KB |
Output is correct |
26 |
Correct |
1526 ms |
11968 KB |
Output is correct |
27 |
Correct |
1696 ms |
12256 KB |
Output is correct |
28 |
Correct |
1667 ms |
12184 KB |
Output is correct |
29 |
Correct |
1393 ms |
11928 KB |
Output is correct |
30 |
Correct |
1818 ms |
12200 KB |
Output is correct |
31 |
Correct |
1831 ms |
12152 KB |
Output is correct |
32 |
Correct |
1816 ms |
12188 KB |
Output is correct |
33 |
Correct |
1736 ms |
12316 KB |
Output is correct |
34 |
Correct |
1770 ms |
12312 KB |
Output is correct |
35 |
Correct |
1718 ms |
11932 KB |
Output is correct |
36 |
Correct |
1460 ms |
12104 KB |
Output is correct |
37 |
Correct |
1465 ms |
12060 KB |
Output is correct |
38 |
Correct |
1448 ms |
12032 KB |
Output is correct |
39 |
Correct |
1122 ms |
9588 KB |
Output is correct |
40 |
Correct |
1145 ms |
9612 KB |
Output is correct |
41 |
Correct |
1129 ms |
9740 KB |
Output is correct |
42 |
Correct |
1445 ms |
14540 KB |
Output is correct |
43 |
Correct |
1373 ms |
14552 KB |
Output is correct |
44 |
Correct |
1415 ms |
14440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
1016 KB |
Output is correct |
2 |
Correct |
29 ms |
1016 KB |
Output is correct |
3 |
Correct |
59 ms |
1656 KB |
Output is correct |
4 |
Correct |
33 ms |
1272 KB |
Output is correct |
5 |
Correct |
99 ms |
1640 KB |
Output is correct |
6 |
Correct |
59 ms |
1528 KB |
Output is correct |
7 |
Correct |
64 ms |
1588 KB |
Output is correct |
8 |
Correct |
60 ms |
1656 KB |
Output is correct |
9 |
Correct |
70 ms |
1528 KB |
Output is correct |
10 |
Correct |
60 ms |
1528 KB |
Output is correct |
11 |
Correct |
62 ms |
1528 KB |
Output is correct |
12 |
Correct |
68 ms |
1532 KB |
Output is correct |
13 |
Correct |
68 ms |
1644 KB |
Output is correct |
14 |
Correct |
64 ms |
1528 KB |
Output is correct |
15 |
Correct |
66 ms |
1604 KB |
Output is correct |
16 |
Correct |
62 ms |
1548 KB |
Output is correct |
17 |
Correct |
61 ms |
1528 KB |
Output is correct |
18 |
Correct |
1508 ms |
12196 KB |
Output is correct |
19 |
Correct |
1482 ms |
12136 KB |
Output is correct |
20 |
Correct |
1487 ms |
12184 KB |
Output is correct |
21 |
Correct |
1439 ms |
12060 KB |
Output is correct |
22 |
Correct |
1456 ms |
12184 KB |
Output is correct |
23 |
Correct |
1705 ms |
12056 KB |
Output is correct |
24 |
Correct |
1612 ms |
12008 KB |
Output is correct |
25 |
Correct |
1571 ms |
12056 KB |
Output is correct |
26 |
Correct |
72 ms |
3192 KB |
Output is correct |
27 |
Correct |
1377 ms |
12204 KB |
Output is correct |
28 |
Correct |
1323 ms |
12200 KB |
Output is correct |
29 |
Correct |
976 ms |
9336 KB |
Output is correct |
30 |
Correct |
1324 ms |
13912 KB |
Output is correct |
31 |
Correct |
1178 ms |
10100 KB |
Output is correct |
32 |
Correct |
739 ms |
7144 KB |
Output is correct |
33 |
Correct |
1174 ms |
10240 KB |
Output is correct |
34 |
Correct |
1121 ms |
10136 KB |
Output is correct |
35 |
Correct |
72 ms |
3196 KB |
Output is correct |
36 |
Correct |
1128 ms |
10008 KB |
Output is correct |
37 |
Correct |
1049 ms |
10012 KB |
Output is correct |
38 |
Correct |
996 ms |
9880 KB |
Output is correct |
39 |
Correct |
706 ms |
7712 KB |
Output is correct |
40 |
Correct |
686 ms |
7600 KB |
Output is correct |
41 |
Correct |
954 ms |
12244 KB |
Output is correct |
42 |
Correct |
929 ms |
12376 KB |
Output is correct |
43 |
Correct |
1502 ms |
12220 KB |
Output is correct |
44 |
Correct |
74 ms |
3448 KB |
Output is correct |
45 |
Correct |
618 ms |
9040 KB |
Output is correct |
46 |
Correct |
629 ms |
9192 KB |
Output is correct |
47 |
Correct |
1426 ms |
12460 KB |
Output is correct |
48 |
Correct |
1505 ms |
12276 KB |
Output is correct |
49 |
Correct |
1441 ms |
12272 KB |
Output is correct |
50 |
Correct |
1035 ms |
8276 KB |
Output is correct |
51 |
Correct |
1068 ms |
8300 KB |
Output is correct |
52 |
Correct |
951 ms |
8468 KB |
Output is correct |
53 |
Correct |
1543 ms |
10424 KB |
Output is correct |
54 |
Correct |
1509 ms |
10224 KB |
Output is correct |
55 |
Correct |
1348 ms |
10476 KB |
Output is correct |
56 |
Correct |
1302 ms |
12496 KB |
Output is correct |
57 |
Correct |
1394 ms |
12528 KB |
Output is correct |
58 |
Correct |
1661 ms |
12140 KB |
Output is correct |
59 |
Correct |
1685 ms |
12272 KB |
Output is correct |
60 |
Correct |
1715 ms |
12268 KB |
Output is correct |
61 |
Correct |
1721 ms |
12180 KB |
Output is correct |
62 |
Correct |
1485 ms |
11240 KB |
Output is correct |
63 |
Correct |
1450 ms |
11244 KB |
Output is correct |
64 |
Correct |
1480 ms |
12144 KB |
Output is correct |
65 |
Correct |
1243 ms |
10784 KB |
Output is correct |
66 |
Correct |
1526 ms |
11968 KB |
Output is correct |
67 |
Correct |
1696 ms |
12256 KB |
Output is correct |
68 |
Correct |
1667 ms |
12184 KB |
Output is correct |
69 |
Correct |
1393 ms |
11928 KB |
Output is correct |
70 |
Correct |
1818 ms |
12200 KB |
Output is correct |
71 |
Correct |
1831 ms |
12152 KB |
Output is correct |
72 |
Correct |
1816 ms |
12188 KB |
Output is correct |
73 |
Correct |
1736 ms |
12316 KB |
Output is correct |
74 |
Correct |
1770 ms |
12312 KB |
Output is correct |
75 |
Correct |
1718 ms |
11932 KB |
Output is correct |
76 |
Correct |
1460 ms |
12104 KB |
Output is correct |
77 |
Correct |
1465 ms |
12060 KB |
Output is correct |
78 |
Correct |
1448 ms |
12032 KB |
Output is correct |
79 |
Correct |
1122 ms |
9588 KB |
Output is correct |
80 |
Correct |
1145 ms |
9612 KB |
Output is correct |
81 |
Correct |
1129 ms |
9740 KB |
Output is correct |
82 |
Correct |
1445 ms |
14540 KB |
Output is correct |
83 |
Correct |
1373 ms |
14552 KB |
Output is correct |
84 |
Correct |
1415 ms |
14440 KB |
Output is correct |
85 |
Correct |
1914 ms |
16536 KB |
Output is correct |
86 |
Correct |
559 ms |
9308 KB |
Output is correct |
87 |
Correct |
552 ms |
9308 KB |
Output is correct |
88 |
Correct |
1513 ms |
16512 KB |
Output is correct |
89 |
Correct |
1850 ms |
16588 KB |
Output is correct |
90 |
Correct |
1519 ms |
16536 KB |
Output is correct |
91 |
Correct |
1721 ms |
12440 KB |
Output is correct |
92 |
Correct |
1692 ms |
12312 KB |
Output is correct |
93 |
Correct |
1819 ms |
12056 KB |
Output is correct |
94 |
Correct |
1961 ms |
13956 KB |
Output is correct |
95 |
Correct |
2005 ms |
14200 KB |
Output is correct |
96 |
Correct |
1655 ms |
14008 KB |
Output is correct |
97 |
Correct |
1449 ms |
13580 KB |
Output is correct |
98 |
Correct |
1346 ms |
17736 KB |
Output is correct |
99 |
Correct |
2044 ms |
16536 KB |
Output is correct |
100 |
Correct |
1999 ms |
16404 KB |
Output is correct |
101 |
Correct |
2088 ms |
16536 KB |
Output is correct |
102 |
Correct |
2108 ms |
16384 KB |
Output is correct |
103 |
Correct |
1726 ms |
16276 KB |
Output is correct |
104 |
Correct |
1743 ms |
16408 KB |
Output is correct |
105 |
Correct |
1807 ms |
16428 KB |
Output is correct |
106 |
Correct |
1679 ms |
16208 KB |
Output is correct |
107 |
Correct |
1553 ms |
11836 KB |
Output is correct |
108 |
Correct |
1772 ms |
16420 KB |
Output is correct |
109 |
Correct |
1361 ms |
14488 KB |
Output is correct |