# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
231204 |
2020-05-13T04:17:46 Z |
ChrisT |
Bridges (APIO19_bridges) |
C++17 |
|
2327 ms |
8768 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e5+4, MOD = 1e9+7, BASE = 31, SQRT = 700;
int p[MN],sz[MN],st[MN],sp;
int find (int n) {return p[n] == n ? n : find(p[n]);}
void merge (int a, int b) {
if ((a=find(a))==(b=find(b))) {st[++sp]=0;return;}
if (sz[a] > sz[b]) swap(a,b);
sz[p[st[++sp]=a]=b] += sz[a];
}
void undo () {
int a = st[sp--];
if (a) {
sz[p[a]] -= sz[a];
p[a] = a;
}
}
void reset(int n) {iota(p+1,p+n+1,1);fill(sz+1,sz+n+1,1);sp=0;}
struct Edge {
int a,b,w,ind;
void read(int _i) {ind=_i;scanf("%d%d%d",&a,&b,&w);}
} edges[MN], temp[MN];
struct Thing {
int a,b,t;
} upd[SQRT+5], query[SQRT+5];
bool seen[MN];
int main () {
int n,m;
scanf ("%d %d",&n,&m);
for (int i = 1; i <= m; i++) edges[i].read(i);
int q; scanf ("%d",&q);
for (int qind = 0; qind < q; qind+=SQRT) {
reset(n);
int ed = min(q,qind+SQRT),qi=0,ui=0; vector<int> change;
for (int i = qind; i < ed; i++) {
int t,a,b;
scanf ("%d %d %d",&t,&a,&b);
if (t == 1) upd[ui++]={a,b,i}, change.push_back(a);
else query[qi++]={a,b,i};
}
sort(all(change)); change.erase(unique(all(change)),change.end()); int ree = change.size(), ti = 0;
int _pp = 0;
for (int i = 1; i <= m; i++) {
if (_pp<ree&&change[_pp]==i)_pp++;
else temp[ti++] = edges[i];
}
sort(temp,temp+ti,[&](const Edge &a, const Edge &b){return a.w<b.w;});
sort(query,query+qi,[&](const Thing &a, const Thing &b){return a.b>b.b;});
--ti;
for (int qq = 0; qq < qi; qq++) {
Thing &cur = query[qq];
while (~ti && temp[ti].w >= cur.b) {
merge(temp[ti].a,temp[ti].b);
--ti;
}
int cnt = 0;
for (int j=ui-1;~j;j--) if(upd[j].t<=cur.t&&!seen[upd[j].a]){
Thing &u = upd[j];
seen[u.a]=1;
if (u.b >= cur.b) ++cnt, merge(edges[u.a].a,edges[u.a].b);
}
for (int i : change) if (!seen[i]&&edges[i].w>=cur.b){
++cnt;
merge(edges[i].a,edges[i].b);
}
cur.a = sz[find(cur.a)];
while (cnt--) undo();
for (int i : change) seen[i]=0;
}
sort(query,query+qi,[&](const Thing &a, const Thing &b){return a.t<b.t;});
for (int i = 0; i < qi; i++) printf ("%d\n",query[i].a);
for (int i = 0; i < ui; i++) {
Thing &u = upd[i];
edges[u.a].w = u.b;
}
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d",&n,&m);
~~~~~~^~~~~~~~~~~~~~~
bridges.cpp:43:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int q; scanf ("%d",&q);
~~~~~~^~~~~~~~~
bridges.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d",&t,&a,&b);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In member function 'void Edge::read(int)':
bridges.cpp:33:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(int _i) {ind=_i;scanf("%d%d%d",&a,&b,&w);}
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
36 ms |
640 KB |
Output is correct |
4 |
Correct |
10 ms |
512 KB |
Output is correct |
5 |
Correct |
23 ms |
512 KB |
Output is correct |
6 |
Correct |
21 ms |
632 KB |
Output is correct |
7 |
Correct |
22 ms |
512 KB |
Output is correct |
8 |
Correct |
23 ms |
512 KB |
Output is correct |
9 |
Correct |
24 ms |
512 KB |
Output is correct |
10 |
Correct |
23 ms |
512 KB |
Output is correct |
11 |
Correct |
22 ms |
572 KB |
Output is correct |
12 |
Correct |
24 ms |
512 KB |
Output is correct |
13 |
Correct |
30 ms |
512 KB |
Output is correct |
14 |
Correct |
28 ms |
512 KB |
Output is correct |
15 |
Correct |
25 ms |
512 KB |
Output is correct |
16 |
Correct |
23 ms |
640 KB |
Output is correct |
17 |
Correct |
23 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1310 ms |
5752 KB |
Output is correct |
2 |
Correct |
1323 ms |
5624 KB |
Output is correct |
3 |
Correct |
1328 ms |
5752 KB |
Output is correct |
4 |
Correct |
1369 ms |
5496 KB |
Output is correct |
5 |
Correct |
1366 ms |
5496 KB |
Output is correct |
6 |
Correct |
1829 ms |
5800 KB |
Output is correct |
7 |
Correct |
1825 ms |
5584 KB |
Output is correct |
8 |
Correct |
1834 ms |
5752 KB |
Output is correct |
9 |
Correct |
60 ms |
2040 KB |
Output is correct |
10 |
Correct |
1041 ms |
4600 KB |
Output is correct |
11 |
Correct |
994 ms |
4768 KB |
Output is correct |
12 |
Correct |
1142 ms |
5676 KB |
Output is correct |
13 |
Correct |
1163 ms |
5752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1042 ms |
4588 KB |
Output is correct |
2 |
Correct |
702 ms |
2684 KB |
Output is correct |
3 |
Correct |
1176 ms |
4216 KB |
Output is correct |
4 |
Correct |
1051 ms |
4496 KB |
Output is correct |
5 |
Correct |
69 ms |
2040 KB |
Output is correct |
6 |
Correct |
1149 ms |
4388 KB |
Output is correct |
7 |
Correct |
1022 ms |
4344 KB |
Output is correct |
8 |
Correct |
909 ms |
4472 KB |
Output is correct |
9 |
Correct |
718 ms |
4732 KB |
Output is correct |
10 |
Correct |
681 ms |
4472 KB |
Output is correct |
11 |
Correct |
747 ms |
4344 KB |
Output is correct |
12 |
Correct |
698 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1776 ms |
8496 KB |
Output is correct |
2 |
Correct |
57 ms |
1912 KB |
Output is correct |
3 |
Correct |
217 ms |
5884 KB |
Output is correct |
4 |
Correct |
113 ms |
5880 KB |
Output is correct |
5 |
Correct |
1008 ms |
7160 KB |
Output is correct |
6 |
Correct |
1737 ms |
8708 KB |
Output is correct |
7 |
Correct |
986 ms |
7288 KB |
Output is correct |
8 |
Correct |
848 ms |
5592 KB |
Output is correct |
9 |
Correct |
831 ms |
5624 KB |
Output is correct |
10 |
Correct |
842 ms |
5624 KB |
Output is correct |
11 |
Correct |
1339 ms |
7032 KB |
Output is correct |
12 |
Correct |
1297 ms |
7104 KB |
Output is correct |
13 |
Correct |
1331 ms |
7160 KB |
Output is correct |
14 |
Correct |
911 ms |
7288 KB |
Output is correct |
15 |
Correct |
971 ms |
7136 KB |
Output is correct |
16 |
Correct |
1802 ms |
8648 KB |
Output is correct |
17 |
Correct |
1827 ms |
8696 KB |
Output is correct |
18 |
Correct |
1781 ms |
8696 KB |
Output is correct |
19 |
Correct |
1751 ms |
8568 KB |
Output is correct |
20 |
Correct |
1513 ms |
7548 KB |
Output is correct |
21 |
Correct |
1508 ms |
7544 KB |
Output is correct |
22 |
Correct |
1734 ms |
8444 KB |
Output is correct |
23 |
Correct |
1036 ms |
6308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1310 ms |
5752 KB |
Output is correct |
2 |
Correct |
1323 ms |
5624 KB |
Output is correct |
3 |
Correct |
1328 ms |
5752 KB |
Output is correct |
4 |
Correct |
1369 ms |
5496 KB |
Output is correct |
5 |
Correct |
1366 ms |
5496 KB |
Output is correct |
6 |
Correct |
1829 ms |
5800 KB |
Output is correct |
7 |
Correct |
1825 ms |
5584 KB |
Output is correct |
8 |
Correct |
1834 ms |
5752 KB |
Output is correct |
9 |
Correct |
60 ms |
2040 KB |
Output is correct |
10 |
Correct |
1041 ms |
4600 KB |
Output is correct |
11 |
Correct |
994 ms |
4768 KB |
Output is correct |
12 |
Correct |
1142 ms |
5676 KB |
Output is correct |
13 |
Correct |
1163 ms |
5752 KB |
Output is correct |
14 |
Correct |
1042 ms |
4588 KB |
Output is correct |
15 |
Correct |
702 ms |
2684 KB |
Output is correct |
16 |
Correct |
1176 ms |
4216 KB |
Output is correct |
17 |
Correct |
1051 ms |
4496 KB |
Output is correct |
18 |
Correct |
69 ms |
2040 KB |
Output is correct |
19 |
Correct |
1149 ms |
4388 KB |
Output is correct |
20 |
Correct |
1022 ms |
4344 KB |
Output is correct |
21 |
Correct |
909 ms |
4472 KB |
Output is correct |
22 |
Correct |
718 ms |
4732 KB |
Output is correct |
23 |
Correct |
681 ms |
4472 KB |
Output is correct |
24 |
Correct |
747 ms |
4344 KB |
Output is correct |
25 |
Correct |
698 ms |
4216 KB |
Output is correct |
26 |
Correct |
1448 ms |
5532 KB |
Output is correct |
27 |
Correct |
1621 ms |
5496 KB |
Output is correct |
28 |
Correct |
1446 ms |
5548 KB |
Output is correct |
29 |
Correct |
1180 ms |
5508 KB |
Output is correct |
30 |
Correct |
1583 ms |
5512 KB |
Output is correct |
31 |
Correct |
1625 ms |
5388 KB |
Output is correct |
32 |
Correct |
1653 ms |
5396 KB |
Output is correct |
33 |
Correct |
1414 ms |
5544 KB |
Output is correct |
34 |
Correct |
1428 ms |
5480 KB |
Output is correct |
35 |
Correct |
1453 ms |
5660 KB |
Output is correct |
36 |
Correct |
1200 ms |
5580 KB |
Output is correct |
37 |
Correct |
1181 ms |
5420 KB |
Output is correct |
38 |
Correct |
1170 ms |
5600 KB |
Output is correct |
39 |
Correct |
945 ms |
5624 KB |
Output is correct |
40 |
Correct |
947 ms |
5624 KB |
Output is correct |
41 |
Correct |
950 ms |
5624 KB |
Output is correct |
42 |
Correct |
945 ms |
5368 KB |
Output is correct |
43 |
Correct |
938 ms |
5344 KB |
Output is correct |
44 |
Correct |
929 ms |
5496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
36 ms |
640 KB |
Output is correct |
4 |
Correct |
10 ms |
512 KB |
Output is correct |
5 |
Correct |
23 ms |
512 KB |
Output is correct |
6 |
Correct |
21 ms |
632 KB |
Output is correct |
7 |
Correct |
22 ms |
512 KB |
Output is correct |
8 |
Correct |
23 ms |
512 KB |
Output is correct |
9 |
Correct |
24 ms |
512 KB |
Output is correct |
10 |
Correct |
23 ms |
512 KB |
Output is correct |
11 |
Correct |
22 ms |
572 KB |
Output is correct |
12 |
Correct |
24 ms |
512 KB |
Output is correct |
13 |
Correct |
30 ms |
512 KB |
Output is correct |
14 |
Correct |
28 ms |
512 KB |
Output is correct |
15 |
Correct |
25 ms |
512 KB |
Output is correct |
16 |
Correct |
23 ms |
640 KB |
Output is correct |
17 |
Correct |
23 ms |
512 KB |
Output is correct |
18 |
Correct |
1310 ms |
5752 KB |
Output is correct |
19 |
Correct |
1323 ms |
5624 KB |
Output is correct |
20 |
Correct |
1328 ms |
5752 KB |
Output is correct |
21 |
Correct |
1369 ms |
5496 KB |
Output is correct |
22 |
Correct |
1366 ms |
5496 KB |
Output is correct |
23 |
Correct |
1829 ms |
5800 KB |
Output is correct |
24 |
Correct |
1825 ms |
5584 KB |
Output is correct |
25 |
Correct |
1834 ms |
5752 KB |
Output is correct |
26 |
Correct |
60 ms |
2040 KB |
Output is correct |
27 |
Correct |
1041 ms |
4600 KB |
Output is correct |
28 |
Correct |
994 ms |
4768 KB |
Output is correct |
29 |
Correct |
1142 ms |
5676 KB |
Output is correct |
30 |
Correct |
1163 ms |
5752 KB |
Output is correct |
31 |
Correct |
1042 ms |
4588 KB |
Output is correct |
32 |
Correct |
702 ms |
2684 KB |
Output is correct |
33 |
Correct |
1176 ms |
4216 KB |
Output is correct |
34 |
Correct |
1051 ms |
4496 KB |
Output is correct |
35 |
Correct |
69 ms |
2040 KB |
Output is correct |
36 |
Correct |
1149 ms |
4388 KB |
Output is correct |
37 |
Correct |
1022 ms |
4344 KB |
Output is correct |
38 |
Correct |
909 ms |
4472 KB |
Output is correct |
39 |
Correct |
718 ms |
4732 KB |
Output is correct |
40 |
Correct |
681 ms |
4472 KB |
Output is correct |
41 |
Correct |
747 ms |
4344 KB |
Output is correct |
42 |
Correct |
698 ms |
4216 KB |
Output is correct |
43 |
Correct |
1776 ms |
8496 KB |
Output is correct |
44 |
Correct |
57 ms |
1912 KB |
Output is correct |
45 |
Correct |
217 ms |
5884 KB |
Output is correct |
46 |
Correct |
113 ms |
5880 KB |
Output is correct |
47 |
Correct |
1008 ms |
7160 KB |
Output is correct |
48 |
Correct |
1737 ms |
8708 KB |
Output is correct |
49 |
Correct |
986 ms |
7288 KB |
Output is correct |
50 |
Correct |
848 ms |
5592 KB |
Output is correct |
51 |
Correct |
831 ms |
5624 KB |
Output is correct |
52 |
Correct |
842 ms |
5624 KB |
Output is correct |
53 |
Correct |
1339 ms |
7032 KB |
Output is correct |
54 |
Correct |
1297 ms |
7104 KB |
Output is correct |
55 |
Correct |
1331 ms |
7160 KB |
Output is correct |
56 |
Correct |
911 ms |
7288 KB |
Output is correct |
57 |
Correct |
971 ms |
7136 KB |
Output is correct |
58 |
Correct |
1802 ms |
8648 KB |
Output is correct |
59 |
Correct |
1827 ms |
8696 KB |
Output is correct |
60 |
Correct |
1781 ms |
8696 KB |
Output is correct |
61 |
Correct |
1751 ms |
8568 KB |
Output is correct |
62 |
Correct |
1513 ms |
7548 KB |
Output is correct |
63 |
Correct |
1508 ms |
7544 KB |
Output is correct |
64 |
Correct |
1734 ms |
8444 KB |
Output is correct |
65 |
Correct |
1036 ms |
6308 KB |
Output is correct |
66 |
Correct |
1448 ms |
5532 KB |
Output is correct |
67 |
Correct |
1621 ms |
5496 KB |
Output is correct |
68 |
Correct |
1446 ms |
5548 KB |
Output is correct |
69 |
Correct |
1180 ms |
5508 KB |
Output is correct |
70 |
Correct |
1583 ms |
5512 KB |
Output is correct |
71 |
Correct |
1625 ms |
5388 KB |
Output is correct |
72 |
Correct |
1653 ms |
5396 KB |
Output is correct |
73 |
Correct |
1414 ms |
5544 KB |
Output is correct |
74 |
Correct |
1428 ms |
5480 KB |
Output is correct |
75 |
Correct |
1453 ms |
5660 KB |
Output is correct |
76 |
Correct |
1200 ms |
5580 KB |
Output is correct |
77 |
Correct |
1181 ms |
5420 KB |
Output is correct |
78 |
Correct |
1170 ms |
5600 KB |
Output is correct |
79 |
Correct |
945 ms |
5624 KB |
Output is correct |
80 |
Correct |
947 ms |
5624 KB |
Output is correct |
81 |
Correct |
950 ms |
5624 KB |
Output is correct |
82 |
Correct |
945 ms |
5368 KB |
Output is correct |
83 |
Correct |
938 ms |
5344 KB |
Output is correct |
84 |
Correct |
929 ms |
5496 KB |
Output is correct |
85 |
Correct |
2259 ms |
8768 KB |
Output is correct |
86 |
Correct |
251 ms |
5880 KB |
Output is correct |
87 |
Correct |
156 ms |
6008 KB |
Output is correct |
88 |
Correct |
1446 ms |
6988 KB |
Output is correct |
89 |
Correct |
2258 ms |
8696 KB |
Output is correct |
90 |
Correct |
1458 ms |
7032 KB |
Output is correct |
91 |
Correct |
1431 ms |
5580 KB |
Output is correct |
92 |
Correct |
1416 ms |
5624 KB |
Output is correct |
93 |
Correct |
1907 ms |
5496 KB |
Output is correct |
94 |
Correct |
1890 ms |
7304 KB |
Output is correct |
95 |
Correct |
1866 ms |
7116 KB |
Output is correct |
96 |
Correct |
2069 ms |
7032 KB |
Output is correct |
97 |
Correct |
1114 ms |
7164 KB |
Output is correct |
98 |
Correct |
1195 ms |
6904 KB |
Output is correct |
99 |
Correct |
2283 ms |
8608 KB |
Output is correct |
100 |
Correct |
2274 ms |
8568 KB |
Output is correct |
101 |
Correct |
2327 ms |
8696 KB |
Output is correct |
102 |
Correct |
2317 ms |
8696 KB |
Output is correct |
103 |
Correct |
2267 ms |
7608 KB |
Output is correct |
104 |
Correct |
2268 ms |
7416 KB |
Output is correct |
105 |
Correct |
1793 ms |
7416 KB |
Output is correct |
106 |
Correct |
1479 ms |
7160 KB |
Output is correct |
107 |
Correct |
1696 ms |
7672 KB |
Output is correct |
108 |
Correct |
2282 ms |
8300 KB |
Output is correct |
109 |
Correct |
1561 ms |
6268 KB |
Output is correct |