# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
383045 |
2021-03-28T18:21:28 Z |
Kerim |
Bridges (APIO19_bridges) |
C++17 |
|
2898 ms |
112508 KB |
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int BLOK=750;
pair<PII,int>edge[MAXN];
pair<int,PII>query[MAXN];
int ans[MAXN],ata[MAXN],sz[MAXN];
bool ban[MAXN],ban1[MAXN];
stack<int>st;
vector<pair<PII,int> >history;
int tap(int x){
if(ata[x]==x)return x;
return tap(ata[x]);
}
bool merge(PII v){
int x=tap(v.ff),y=tap(v.ss);
if(x==y)return 0;
if(x<y)swap(x,y);
history.pb(mp(mp(x,y),sz[y]));
ata[y]=x;sz[x]+=sz[y]; return 1;
}
int main(){
//freopen("file.in", "r", stdin);
int n,m;
scanf("%d%d",&n,&m);
set<PII>edges;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[i]=mp(mp(u,v),w);
edges.insert(mp(w,i));
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++){
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
query[i]=mp(t,mp(a,b));
}
for(int i=1;i<=q;i+=BLOK){
memset(ban,0,sizeof ban);
for(int i=1;i<=n;i++)ata[i]=i,sz[i]=1;
vector<PII>v,g;int r=min(i+BLOK-1,q);
for(int j=i;j<=r;j++){
if(query[j].ff==1)
ban[query[j].ss.ff]=j;
else
g.pb(mp(query[j].ss.ss,j));
}
tr(it,edges)
if(!ban[it->ss])
v.pb(*it);
sort(all(g));
int p=int(v.size())-1,rec;
for(int j=int(g.size())-1,ind,k;j>=0;j--){
rec=0;
while(p>=0 and v[p].ff>=g[j].ff)
merge(edge[v[p].ss].ff),p--;
for(k=g[j].ss-1;k>=i;k--){
ind=query[k].ss.ff;
if(query[k].ff==1 and !ban1[ind]){
if(query[k].ss.ss>=g[j].ff)rec+=merge(edge[ind].ff);
ban1[ind]=1;st.push(ind);
}
}
for(k=g[j].ss+1;k<=r;k++){
ind=query[k].ss.ff;
if(query[k].ff==1 and !ban1[ind]){
if(edge[ind].ss>=g[j].ff)rec+=merge(edge[ind].ff);
ban1[ind]=1;st.push(ind);
}
}
ans[g[j].ss]=sz[tap(query[g[j].ss].ss.ff)];
while(!st.empty())ban1[st.top()]=0,st.pop();
while(rec--){ //x,y,sz[y]
int y=history.back().ff.ss;
sz[history.back().ff.ff]-=history.back().ss;ata[y]=y;
history.ppb();
}
}
for(int j=i,a;j<=r;j++)
if(query[j].ff==1){
a=query[j].ss.ff;
edges.erase(mp(edge[a].ss,a));
edge[a].ss=query[j].ss.ss;
edges.insert(mp(edge[a].ss,a));
}
}
for(int i=1;i<=q;i++)
if(query[i].ff==2)
printf("%d\n",ans[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:105:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
105 | for(int i=1;i<=q;i++)
| ^~~
bridges.cpp:108:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
108 | return 0;
| ^~~~~~
bridges.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
41 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
bridges.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
45 | scanf("%d%d%d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
bridges.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%d%d%d",&t,&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
41 ms |
748 KB |
Output is correct |
4 |
Correct |
12 ms |
620 KB |
Output is correct |
5 |
Correct |
30 ms |
620 KB |
Output is correct |
6 |
Correct |
33 ms |
620 KB |
Output is correct |
7 |
Correct |
31 ms |
620 KB |
Output is correct |
8 |
Correct |
28 ms |
620 KB |
Output is correct |
9 |
Correct |
27 ms |
620 KB |
Output is correct |
10 |
Correct |
27 ms |
632 KB |
Output is correct |
11 |
Correct |
27 ms |
748 KB |
Output is correct |
12 |
Correct |
28 ms |
620 KB |
Output is correct |
13 |
Correct |
36 ms |
620 KB |
Output is correct |
14 |
Correct |
34 ms |
620 KB |
Output is correct |
15 |
Correct |
32 ms |
620 KB |
Output is correct |
16 |
Correct |
27 ms |
620 KB |
Output is correct |
17 |
Correct |
27 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1541 ms |
104596 KB |
Output is correct |
2 |
Correct |
1414 ms |
104832 KB |
Output is correct |
3 |
Correct |
1462 ms |
104696 KB |
Output is correct |
4 |
Correct |
1556 ms |
104828 KB |
Output is correct |
5 |
Correct |
1562 ms |
104816 KB |
Output is correct |
6 |
Correct |
2168 ms |
104764 KB |
Output is correct |
7 |
Correct |
2077 ms |
104684 KB |
Output is correct |
8 |
Correct |
2105 ms |
104724 KB |
Output is correct |
9 |
Correct |
108 ms |
2156 KB |
Output is correct |
10 |
Correct |
1153 ms |
104840 KB |
Output is correct |
11 |
Correct |
1111 ms |
104684 KB |
Output is correct |
12 |
Correct |
1304 ms |
104908 KB |
Output is correct |
13 |
Correct |
1299 ms |
104764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1278 ms |
103480 KB |
Output is correct |
2 |
Correct |
1175 ms |
27812 KB |
Output is correct |
3 |
Correct |
1858 ms |
103668 KB |
Output is correct |
4 |
Correct |
1275 ms |
103284 KB |
Output is correct |
5 |
Correct |
182 ms |
2156 KB |
Output is correct |
6 |
Correct |
1634 ms |
103304 KB |
Output is correct |
7 |
Correct |
1354 ms |
103220 KB |
Output is correct |
8 |
Correct |
1180 ms |
103176 KB |
Output is correct |
9 |
Correct |
967 ms |
103276 KB |
Output is correct |
10 |
Correct |
853 ms |
103292 KB |
Output is correct |
11 |
Correct |
1027 ms |
103288 KB |
Output is correct |
12 |
Correct |
891 ms |
103332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2000 ms |
108700 KB |
Output is correct |
2 |
Correct |
102 ms |
2156 KB |
Output is correct |
3 |
Correct |
230 ms |
8408 KB |
Output is correct |
4 |
Correct |
153 ms |
8420 KB |
Output is correct |
5 |
Correct |
1426 ms |
108736 KB |
Output is correct |
6 |
Correct |
1966 ms |
108504 KB |
Output is correct |
7 |
Correct |
1359 ms |
108504 KB |
Output is correct |
8 |
Correct |
833 ms |
104584 KB |
Output is correct |
9 |
Correct |
828 ms |
104556 KB |
Output is correct |
10 |
Correct |
844 ms |
104716 KB |
Output is correct |
11 |
Correct |
1365 ms |
106968 KB |
Output is correct |
12 |
Correct |
1398 ms |
107272 KB |
Output is correct |
13 |
Correct |
1379 ms |
106836 KB |
Output is correct |
14 |
Correct |
1227 ms |
108676 KB |
Output is correct |
15 |
Correct |
1354 ms |
108568 KB |
Output is correct |
16 |
Correct |
1949 ms |
108552 KB |
Output is correct |
17 |
Correct |
1946 ms |
108484 KB |
Output is correct |
18 |
Correct |
1958 ms |
108616 KB |
Output is correct |
19 |
Correct |
1942 ms |
108452 KB |
Output is correct |
20 |
Correct |
1560 ms |
107476 KB |
Output is correct |
21 |
Correct |
1574 ms |
107652 KB |
Output is correct |
22 |
Correct |
2031 ms |
108312 KB |
Output is correct |
23 |
Correct |
1340 ms |
107300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1541 ms |
104596 KB |
Output is correct |
2 |
Correct |
1414 ms |
104832 KB |
Output is correct |
3 |
Correct |
1462 ms |
104696 KB |
Output is correct |
4 |
Correct |
1556 ms |
104828 KB |
Output is correct |
5 |
Correct |
1562 ms |
104816 KB |
Output is correct |
6 |
Correct |
2168 ms |
104764 KB |
Output is correct |
7 |
Correct |
2077 ms |
104684 KB |
Output is correct |
8 |
Correct |
2105 ms |
104724 KB |
Output is correct |
9 |
Correct |
108 ms |
2156 KB |
Output is correct |
10 |
Correct |
1153 ms |
104840 KB |
Output is correct |
11 |
Correct |
1111 ms |
104684 KB |
Output is correct |
12 |
Correct |
1304 ms |
104908 KB |
Output is correct |
13 |
Correct |
1299 ms |
104764 KB |
Output is correct |
14 |
Correct |
1278 ms |
103480 KB |
Output is correct |
15 |
Correct |
1175 ms |
27812 KB |
Output is correct |
16 |
Correct |
1858 ms |
103668 KB |
Output is correct |
17 |
Correct |
1275 ms |
103284 KB |
Output is correct |
18 |
Correct |
182 ms |
2156 KB |
Output is correct |
19 |
Correct |
1634 ms |
103304 KB |
Output is correct |
20 |
Correct |
1354 ms |
103220 KB |
Output is correct |
21 |
Correct |
1180 ms |
103176 KB |
Output is correct |
22 |
Correct |
967 ms |
103276 KB |
Output is correct |
23 |
Correct |
853 ms |
103292 KB |
Output is correct |
24 |
Correct |
1027 ms |
103288 KB |
Output is correct |
25 |
Correct |
891 ms |
103332 KB |
Output is correct |
26 |
Correct |
1699 ms |
104780 KB |
Output is correct |
27 |
Correct |
1938 ms |
104916 KB |
Output is correct |
28 |
Correct |
1617 ms |
104708 KB |
Output is correct |
29 |
Correct |
1294 ms |
104812 KB |
Output is correct |
30 |
Correct |
1697 ms |
104996 KB |
Output is correct |
31 |
Correct |
1773 ms |
104892 KB |
Output is correct |
32 |
Correct |
1796 ms |
104872 KB |
Output is correct |
33 |
Correct |
1570 ms |
104684 KB |
Output is correct |
34 |
Correct |
1560 ms |
104936 KB |
Output is correct |
35 |
Correct |
1646 ms |
104888 KB |
Output is correct |
36 |
Correct |
1349 ms |
104684 KB |
Output is correct |
37 |
Correct |
1257 ms |
104776 KB |
Output is correct |
38 |
Correct |
1236 ms |
104696 KB |
Output is correct |
39 |
Correct |
1116 ms |
104736 KB |
Output is correct |
40 |
Correct |
1012 ms |
104672 KB |
Output is correct |
41 |
Correct |
1026 ms |
104812 KB |
Output is correct |
42 |
Correct |
1061 ms |
104684 KB |
Output is correct |
43 |
Correct |
990 ms |
104692 KB |
Output is correct |
44 |
Correct |
961 ms |
104672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
41 ms |
748 KB |
Output is correct |
4 |
Correct |
12 ms |
620 KB |
Output is correct |
5 |
Correct |
30 ms |
620 KB |
Output is correct |
6 |
Correct |
33 ms |
620 KB |
Output is correct |
7 |
Correct |
31 ms |
620 KB |
Output is correct |
8 |
Correct |
28 ms |
620 KB |
Output is correct |
9 |
Correct |
27 ms |
620 KB |
Output is correct |
10 |
Correct |
27 ms |
632 KB |
Output is correct |
11 |
Correct |
27 ms |
748 KB |
Output is correct |
12 |
Correct |
28 ms |
620 KB |
Output is correct |
13 |
Correct |
36 ms |
620 KB |
Output is correct |
14 |
Correct |
34 ms |
620 KB |
Output is correct |
15 |
Correct |
32 ms |
620 KB |
Output is correct |
16 |
Correct |
27 ms |
620 KB |
Output is correct |
17 |
Correct |
27 ms |
620 KB |
Output is correct |
18 |
Correct |
1541 ms |
104596 KB |
Output is correct |
19 |
Correct |
1414 ms |
104832 KB |
Output is correct |
20 |
Correct |
1462 ms |
104696 KB |
Output is correct |
21 |
Correct |
1556 ms |
104828 KB |
Output is correct |
22 |
Correct |
1562 ms |
104816 KB |
Output is correct |
23 |
Correct |
2168 ms |
104764 KB |
Output is correct |
24 |
Correct |
2077 ms |
104684 KB |
Output is correct |
25 |
Correct |
2105 ms |
104724 KB |
Output is correct |
26 |
Correct |
108 ms |
2156 KB |
Output is correct |
27 |
Correct |
1153 ms |
104840 KB |
Output is correct |
28 |
Correct |
1111 ms |
104684 KB |
Output is correct |
29 |
Correct |
1304 ms |
104908 KB |
Output is correct |
30 |
Correct |
1299 ms |
104764 KB |
Output is correct |
31 |
Correct |
1278 ms |
103480 KB |
Output is correct |
32 |
Correct |
1175 ms |
27812 KB |
Output is correct |
33 |
Correct |
1858 ms |
103668 KB |
Output is correct |
34 |
Correct |
1275 ms |
103284 KB |
Output is correct |
35 |
Correct |
182 ms |
2156 KB |
Output is correct |
36 |
Correct |
1634 ms |
103304 KB |
Output is correct |
37 |
Correct |
1354 ms |
103220 KB |
Output is correct |
38 |
Correct |
1180 ms |
103176 KB |
Output is correct |
39 |
Correct |
967 ms |
103276 KB |
Output is correct |
40 |
Correct |
853 ms |
103292 KB |
Output is correct |
41 |
Correct |
1027 ms |
103288 KB |
Output is correct |
42 |
Correct |
891 ms |
103332 KB |
Output is correct |
43 |
Correct |
2000 ms |
108700 KB |
Output is correct |
44 |
Correct |
102 ms |
2156 KB |
Output is correct |
45 |
Correct |
230 ms |
8408 KB |
Output is correct |
46 |
Correct |
153 ms |
8420 KB |
Output is correct |
47 |
Correct |
1426 ms |
108736 KB |
Output is correct |
48 |
Correct |
1966 ms |
108504 KB |
Output is correct |
49 |
Correct |
1359 ms |
108504 KB |
Output is correct |
50 |
Correct |
833 ms |
104584 KB |
Output is correct |
51 |
Correct |
828 ms |
104556 KB |
Output is correct |
52 |
Correct |
844 ms |
104716 KB |
Output is correct |
53 |
Correct |
1365 ms |
106968 KB |
Output is correct |
54 |
Correct |
1398 ms |
107272 KB |
Output is correct |
55 |
Correct |
1379 ms |
106836 KB |
Output is correct |
56 |
Correct |
1227 ms |
108676 KB |
Output is correct |
57 |
Correct |
1354 ms |
108568 KB |
Output is correct |
58 |
Correct |
1949 ms |
108552 KB |
Output is correct |
59 |
Correct |
1946 ms |
108484 KB |
Output is correct |
60 |
Correct |
1958 ms |
108616 KB |
Output is correct |
61 |
Correct |
1942 ms |
108452 KB |
Output is correct |
62 |
Correct |
1560 ms |
107476 KB |
Output is correct |
63 |
Correct |
1574 ms |
107652 KB |
Output is correct |
64 |
Correct |
2031 ms |
108312 KB |
Output is correct |
65 |
Correct |
1340 ms |
107300 KB |
Output is correct |
66 |
Correct |
1699 ms |
104780 KB |
Output is correct |
67 |
Correct |
1938 ms |
104916 KB |
Output is correct |
68 |
Correct |
1617 ms |
104708 KB |
Output is correct |
69 |
Correct |
1294 ms |
104812 KB |
Output is correct |
70 |
Correct |
1697 ms |
104996 KB |
Output is correct |
71 |
Correct |
1773 ms |
104892 KB |
Output is correct |
72 |
Correct |
1796 ms |
104872 KB |
Output is correct |
73 |
Correct |
1570 ms |
104684 KB |
Output is correct |
74 |
Correct |
1560 ms |
104936 KB |
Output is correct |
75 |
Correct |
1646 ms |
104888 KB |
Output is correct |
76 |
Correct |
1349 ms |
104684 KB |
Output is correct |
77 |
Correct |
1257 ms |
104776 KB |
Output is correct |
78 |
Correct |
1236 ms |
104696 KB |
Output is correct |
79 |
Correct |
1116 ms |
104736 KB |
Output is correct |
80 |
Correct |
1012 ms |
104672 KB |
Output is correct |
81 |
Correct |
1026 ms |
104812 KB |
Output is correct |
82 |
Correct |
1061 ms |
104684 KB |
Output is correct |
83 |
Correct |
990 ms |
104692 KB |
Output is correct |
84 |
Correct |
961 ms |
104672 KB |
Output is correct |
85 |
Correct |
2756 ms |
108900 KB |
Output is correct |
86 |
Correct |
291 ms |
10332 KB |
Output is correct |
87 |
Correct |
211 ms |
10456 KB |
Output is correct |
88 |
Correct |
2139 ms |
110804 KB |
Output is correct |
89 |
Correct |
2625 ms |
112472 KB |
Output is correct |
90 |
Correct |
2119 ms |
110820 KB |
Output is correct |
91 |
Correct |
1510 ms |
107536 KB |
Output is correct |
92 |
Correct |
1517 ms |
107500 KB |
Output is correct |
93 |
Correct |
1983 ms |
107252 KB |
Output is correct |
94 |
Correct |
2088 ms |
110300 KB |
Output is correct |
95 |
Correct |
2015 ms |
110300 KB |
Output is correct |
96 |
Correct |
2459 ms |
110224 KB |
Output is correct |
97 |
Correct |
1661 ms |
110924 KB |
Output is correct |
98 |
Correct |
1718 ms |
110860 KB |
Output is correct |
99 |
Correct |
2770 ms |
112356 KB |
Output is correct |
100 |
Correct |
2618 ms |
112304 KB |
Output is correct |
101 |
Correct |
2635 ms |
112364 KB |
Output is correct |
102 |
Correct |
2573 ms |
112508 KB |
Output is correct |
103 |
Correct |
2709 ms |
110820 KB |
Output is correct |
104 |
Correct |
2676 ms |
110860 KB |
Output is correct |
105 |
Correct |
2025 ms |
110840 KB |
Output is correct |
106 |
Correct |
1594 ms |
110172 KB |
Output is correct |
107 |
Correct |
1948 ms |
110676 KB |
Output is correct |
108 |
Correct |
2898 ms |
111968 KB |
Output is correct |
109 |
Correct |
2201 ms |
109452 KB |
Output is correct |