# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
125242 |
2019-07-04T21:57:05 Z |
tri |
Bridges (APIO19_bridges) |
C++14 |
|
2930 ms |
20856 KB |
#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];
void init() {
for (int i = 0; i < MAXN; i++) {
anc[i] = i;
sz[i] = 1;
}
}
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;
}
anc[a] = b;
sz[b] += sz[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:150:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nxtQ < cQs.size() && get<0>(cQs[nxtQ]) > oW) {
~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
760 KB |
Output is correct |
2 |
Correct |
13 ms |
764 KB |
Output is correct |
3 |
Correct |
48 ms |
1388 KB |
Output is correct |
4 |
Correct |
17 ms |
1016 KB |
Output is correct |
5 |
Correct |
47 ms |
1272 KB |
Output is correct |
6 |
Correct |
47 ms |
1272 KB |
Output is correct |
7 |
Correct |
47 ms |
1272 KB |
Output is correct |
8 |
Correct |
44 ms |
1272 KB |
Output is correct |
9 |
Correct |
53 ms |
1272 KB |
Output is correct |
10 |
Correct |
44 ms |
1272 KB |
Output is correct |
11 |
Correct |
43 ms |
1276 KB |
Output is correct |
12 |
Correct |
45 ms |
1272 KB |
Output is correct |
13 |
Correct |
51 ms |
1400 KB |
Output is correct |
14 |
Correct |
48 ms |
1272 KB |
Output is correct |
15 |
Correct |
51 ms |
1272 KB |
Output is correct |
16 |
Correct |
47 ms |
1272 KB |
Output is correct |
17 |
Correct |
46 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1310 ms |
11792 KB |
Output is correct |
2 |
Correct |
1246 ms |
11812 KB |
Output is correct |
3 |
Correct |
1277 ms |
11800 KB |
Output is correct |
4 |
Correct |
1265 ms |
11932 KB |
Output is correct |
5 |
Correct |
1240 ms |
11800 KB |
Output is correct |
6 |
Correct |
1466 ms |
11724 KB |
Output is correct |
7 |
Correct |
1385 ms |
11800 KB |
Output is correct |
8 |
Correct |
1346 ms |
11676 KB |
Output is correct |
9 |
Correct |
62 ms |
2936 KB |
Output is correct |
10 |
Correct |
1193 ms |
11804 KB |
Output is correct |
11 |
Correct |
1141 ms |
11656 KB |
Output is correct |
12 |
Correct |
935 ms |
9292 KB |
Output is correct |
13 |
Correct |
1111 ms |
14320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1338 ms |
12060 KB |
Output is correct |
2 |
Correct |
843 ms |
9108 KB |
Output is correct |
3 |
Correct |
1503 ms |
14364 KB |
Output is correct |
4 |
Correct |
1426 ms |
17180 KB |
Output is correct |
5 |
Correct |
56 ms |
2808 KB |
Output is correct |
6 |
Correct |
1556 ms |
15492 KB |
Output is correct |
7 |
Correct |
1411 ms |
15284 KB |
Output is correct |
8 |
Correct |
1264 ms |
13468 KB |
Output is correct |
9 |
Correct |
1006 ms |
9120 KB |
Output is correct |
10 |
Correct |
900 ms |
8548 KB |
Output is correct |
11 |
Correct |
1244 ms |
17268 KB |
Output is correct |
12 |
Correct |
1200 ms |
15192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2531 ms |
11756 KB |
Output is correct |
2 |
Correct |
57 ms |
3576 KB |
Output is correct |
3 |
Correct |
600 ms |
9192 KB |
Output is correct |
4 |
Correct |
613 ms |
9168 KB |
Output is correct |
5 |
Correct |
2135 ms |
12276 KB |
Output is correct |
6 |
Correct |
2624 ms |
12272 KB |
Output is correct |
7 |
Correct |
2230 ms |
12368 KB |
Output is correct |
8 |
Correct |
919 ms |
8316 KB |
Output is correct |
9 |
Correct |
937 ms |
8316 KB |
Output is correct |
10 |
Correct |
842 ms |
8440 KB |
Output is correct |
11 |
Correct |
1535 ms |
10296 KB |
Output is correct |
12 |
Correct |
1538 ms |
10224 KB |
Output is correct |
13 |
Correct |
1320 ms |
10440 KB |
Output is correct |
14 |
Correct |
1942 ms |
12520 KB |
Output is correct |
15 |
Correct |
2065 ms |
12400 KB |
Output is correct |
16 |
Correct |
2393 ms |
12136 KB |
Output is correct |
17 |
Correct |
2403 ms |
12272 KB |
Output is correct |
18 |
Correct |
2295 ms |
12188 KB |
Output is correct |
19 |
Correct |
2305 ms |
12268 KB |
Output is correct |
20 |
Correct |
1540 ms |
10992 KB |
Output is correct |
21 |
Correct |
1508 ms |
11072 KB |
Output is correct |
22 |
Correct |
2173 ms |
11944 KB |
Output is correct |
23 |
Correct |
1585 ms |
10860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1310 ms |
11792 KB |
Output is correct |
2 |
Correct |
1246 ms |
11812 KB |
Output is correct |
3 |
Correct |
1277 ms |
11800 KB |
Output is correct |
4 |
Correct |
1265 ms |
11932 KB |
Output is correct |
5 |
Correct |
1240 ms |
11800 KB |
Output is correct |
6 |
Correct |
1466 ms |
11724 KB |
Output is correct |
7 |
Correct |
1385 ms |
11800 KB |
Output is correct |
8 |
Correct |
1346 ms |
11676 KB |
Output is correct |
9 |
Correct |
62 ms |
2936 KB |
Output is correct |
10 |
Correct |
1193 ms |
11804 KB |
Output is correct |
11 |
Correct |
1141 ms |
11656 KB |
Output is correct |
12 |
Correct |
935 ms |
9292 KB |
Output is correct |
13 |
Correct |
1111 ms |
14320 KB |
Output is correct |
14 |
Correct |
1338 ms |
12060 KB |
Output is correct |
15 |
Correct |
843 ms |
9108 KB |
Output is correct |
16 |
Correct |
1503 ms |
14364 KB |
Output is correct |
17 |
Correct |
1426 ms |
17180 KB |
Output is correct |
18 |
Correct |
56 ms |
2808 KB |
Output is correct |
19 |
Correct |
1556 ms |
15492 KB |
Output is correct |
20 |
Correct |
1411 ms |
15284 KB |
Output is correct |
21 |
Correct |
1264 ms |
13468 KB |
Output is correct |
22 |
Correct |
1006 ms |
9120 KB |
Output is correct |
23 |
Correct |
900 ms |
8548 KB |
Output is correct |
24 |
Correct |
1244 ms |
17268 KB |
Output is correct |
25 |
Correct |
1200 ms |
15192 KB |
Output is correct |
26 |
Correct |
2182 ms |
15088 KB |
Output is correct |
27 |
Correct |
1989 ms |
13464 KB |
Output is correct |
28 |
Correct |
1997 ms |
16372 KB |
Output is correct |
29 |
Correct |
1609 ms |
13336 KB |
Output is correct |
30 |
Correct |
1927 ms |
11932 KB |
Output is correct |
31 |
Correct |
1999 ms |
12060 KB |
Output is correct |
32 |
Correct |
1864 ms |
11836 KB |
Output is correct |
33 |
Correct |
1684 ms |
11928 KB |
Output is correct |
34 |
Correct |
1724 ms |
11800 KB |
Output is correct |
35 |
Correct |
1694 ms |
11840 KB |
Output is correct |
36 |
Correct |
1443 ms |
11800 KB |
Output is correct |
37 |
Correct |
1469 ms |
11816 KB |
Output is correct |
38 |
Correct |
1452 ms |
11816 KB |
Output is correct |
39 |
Correct |
1089 ms |
9480 KB |
Output is correct |
40 |
Correct |
1098 ms |
9584 KB |
Output is correct |
41 |
Correct |
1144 ms |
9508 KB |
Output is correct |
42 |
Correct |
1366 ms |
14292 KB |
Output is correct |
43 |
Correct |
1419 ms |
14332 KB |
Output is correct |
44 |
Correct |
1336 ms |
14288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
760 KB |
Output is correct |
2 |
Correct |
13 ms |
764 KB |
Output is correct |
3 |
Correct |
48 ms |
1388 KB |
Output is correct |
4 |
Correct |
17 ms |
1016 KB |
Output is correct |
5 |
Correct |
47 ms |
1272 KB |
Output is correct |
6 |
Correct |
47 ms |
1272 KB |
Output is correct |
7 |
Correct |
47 ms |
1272 KB |
Output is correct |
8 |
Correct |
44 ms |
1272 KB |
Output is correct |
9 |
Correct |
53 ms |
1272 KB |
Output is correct |
10 |
Correct |
44 ms |
1272 KB |
Output is correct |
11 |
Correct |
43 ms |
1276 KB |
Output is correct |
12 |
Correct |
45 ms |
1272 KB |
Output is correct |
13 |
Correct |
51 ms |
1400 KB |
Output is correct |
14 |
Correct |
48 ms |
1272 KB |
Output is correct |
15 |
Correct |
51 ms |
1272 KB |
Output is correct |
16 |
Correct |
47 ms |
1272 KB |
Output is correct |
17 |
Correct |
46 ms |
1272 KB |
Output is correct |
18 |
Correct |
1310 ms |
11792 KB |
Output is correct |
19 |
Correct |
1246 ms |
11812 KB |
Output is correct |
20 |
Correct |
1277 ms |
11800 KB |
Output is correct |
21 |
Correct |
1265 ms |
11932 KB |
Output is correct |
22 |
Correct |
1240 ms |
11800 KB |
Output is correct |
23 |
Correct |
1466 ms |
11724 KB |
Output is correct |
24 |
Correct |
1385 ms |
11800 KB |
Output is correct |
25 |
Correct |
1346 ms |
11676 KB |
Output is correct |
26 |
Correct |
62 ms |
2936 KB |
Output is correct |
27 |
Correct |
1193 ms |
11804 KB |
Output is correct |
28 |
Correct |
1141 ms |
11656 KB |
Output is correct |
29 |
Correct |
935 ms |
9292 KB |
Output is correct |
30 |
Correct |
1111 ms |
14320 KB |
Output is correct |
31 |
Correct |
1338 ms |
12060 KB |
Output is correct |
32 |
Correct |
843 ms |
9108 KB |
Output is correct |
33 |
Correct |
1503 ms |
14364 KB |
Output is correct |
34 |
Correct |
1426 ms |
17180 KB |
Output is correct |
35 |
Correct |
56 ms |
2808 KB |
Output is correct |
36 |
Correct |
1556 ms |
15492 KB |
Output is correct |
37 |
Correct |
1411 ms |
15284 KB |
Output is correct |
38 |
Correct |
1264 ms |
13468 KB |
Output is correct |
39 |
Correct |
1006 ms |
9120 KB |
Output is correct |
40 |
Correct |
900 ms |
8548 KB |
Output is correct |
41 |
Correct |
1244 ms |
17268 KB |
Output is correct |
42 |
Correct |
1200 ms |
15192 KB |
Output is correct |
43 |
Correct |
2531 ms |
11756 KB |
Output is correct |
44 |
Correct |
57 ms |
3576 KB |
Output is correct |
45 |
Correct |
600 ms |
9192 KB |
Output is correct |
46 |
Correct |
613 ms |
9168 KB |
Output is correct |
47 |
Correct |
2135 ms |
12276 KB |
Output is correct |
48 |
Correct |
2624 ms |
12272 KB |
Output is correct |
49 |
Correct |
2230 ms |
12368 KB |
Output is correct |
50 |
Correct |
919 ms |
8316 KB |
Output is correct |
51 |
Correct |
937 ms |
8316 KB |
Output is correct |
52 |
Correct |
842 ms |
8440 KB |
Output is correct |
53 |
Correct |
1535 ms |
10296 KB |
Output is correct |
54 |
Correct |
1538 ms |
10224 KB |
Output is correct |
55 |
Correct |
1320 ms |
10440 KB |
Output is correct |
56 |
Correct |
1942 ms |
12520 KB |
Output is correct |
57 |
Correct |
2065 ms |
12400 KB |
Output is correct |
58 |
Correct |
2393 ms |
12136 KB |
Output is correct |
59 |
Correct |
2403 ms |
12272 KB |
Output is correct |
60 |
Correct |
2295 ms |
12188 KB |
Output is correct |
61 |
Correct |
2305 ms |
12268 KB |
Output is correct |
62 |
Correct |
1540 ms |
10992 KB |
Output is correct |
63 |
Correct |
1508 ms |
11072 KB |
Output is correct |
64 |
Correct |
2173 ms |
11944 KB |
Output is correct |
65 |
Correct |
1585 ms |
10860 KB |
Output is correct |
66 |
Correct |
2182 ms |
15088 KB |
Output is correct |
67 |
Correct |
1989 ms |
13464 KB |
Output is correct |
68 |
Correct |
1997 ms |
16372 KB |
Output is correct |
69 |
Correct |
1609 ms |
13336 KB |
Output is correct |
70 |
Correct |
1927 ms |
11932 KB |
Output is correct |
71 |
Correct |
1999 ms |
12060 KB |
Output is correct |
72 |
Correct |
1864 ms |
11836 KB |
Output is correct |
73 |
Correct |
1684 ms |
11928 KB |
Output is correct |
74 |
Correct |
1724 ms |
11800 KB |
Output is correct |
75 |
Correct |
1694 ms |
11840 KB |
Output is correct |
76 |
Correct |
1443 ms |
11800 KB |
Output is correct |
77 |
Correct |
1469 ms |
11816 KB |
Output is correct |
78 |
Correct |
1452 ms |
11816 KB |
Output is correct |
79 |
Correct |
1089 ms |
9480 KB |
Output is correct |
80 |
Correct |
1098 ms |
9584 KB |
Output is correct |
81 |
Correct |
1144 ms |
9508 KB |
Output is correct |
82 |
Correct |
1366 ms |
14292 KB |
Output is correct |
83 |
Correct |
1419 ms |
14332 KB |
Output is correct |
84 |
Correct |
1336 ms |
14288 KB |
Output is correct |
85 |
Correct |
2914 ms |
20732 KB |
Output is correct |
86 |
Correct |
544 ms |
10864 KB |
Output is correct |
87 |
Correct |
540 ms |
10716 KB |
Output is correct |
88 |
Correct |
2304 ms |
18556 KB |
Output is correct |
89 |
Correct |
2930 ms |
20856 KB |
Output is correct |
90 |
Correct |
2158 ms |
18456 KB |
Output is correct |
91 |
Correct |
1552 ms |
14620 KB |
Output is correct |
92 |
Correct |
1569 ms |
14744 KB |
Output is correct |
93 |
Correct |
1638 ms |
14208 KB |
Output is correct |
94 |
Correct |
2045 ms |
16980 KB |
Output is correct |
95 |
Correct |
1993 ms |
17044 KB |
Output is correct |
96 |
Correct |
1676 ms |
16724 KB |
Output is correct |
97 |
Correct |
2149 ms |
14944 KB |
Output is correct |
98 |
Correct |
2025 ms |
19516 KB |
Output is correct |
99 |
Correct |
2718 ms |
19964 KB |
Output is correct |
100 |
Correct |
2706 ms |
19940 KB |
Output is correct |
101 |
Correct |
2610 ms |
20244 KB |
Output is correct |
102 |
Correct |
2716 ms |
20020 KB |
Output is correct |
103 |
Correct |
1753 ms |
19348 KB |
Output is correct |
104 |
Correct |
1782 ms |
19352 KB |
Output is correct |
105 |
Correct |
1748 ms |
19244 KB |
Output is correct |
106 |
Correct |
1599 ms |
18900 KB |
Output is correct |
107 |
Correct |
1512 ms |
14624 KB |
Output is correct |
108 |
Correct |
2287 ms |
19732 KB |
Output is correct |
109 |
Correct |
1586 ms |
16152 KB |
Output is correct |