oj.uz

Submission #535071

# Submission time Handle Problem Language Result Execution time Memory
535071 2022-03-09T11:05:32 Z new_acc Bridges (APIO19_bridges) C++14
100 / 100
 2029 ms 9340 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
struct st{
	int a,b,c;
};
int fau[N],siz[N],c[N],res[N];
pair<int,int>w[N];
bitset<N>pom;
bitset<N>pom2;
vi roolf;
st zap[N];
int Find(int a){
	while(fau[a]!=a) a=fau[a];
	return a;
}
void Union(int a,int b,bool xd){
	a=Find(a),b=Find(b);
	if(a==b) return;
	if(siz[a]>siz[b]) swap(a,b);
	fau[a]=b,siz[b]+=siz[a];
	if(xd) roolf.push_back(a);
}
void rollback(){
	while(roolf.size()){
		int u=roolf.back();
		roolf.pop_back();
		siz[fau[u]]-=siz[u];
		fau[u]=u;
	}
}	
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) fau[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++) cin>>w[i].fi>>w[i].se>>c[i];
	int q;
	cin>>q;
	for(int i=1;i<=q;i++) cin>>zap[i].a>>zap[i].b>>zap[i].c;
	int p=1000;
	for(int i=1;i<=q;i+=p){
		vector<pair<int,int> >sorted;
		vector<pair<int,int> >aktz;
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) pom[zap[j].b]=1;
			else aktz.push_back({zap[j].c,j});
		}
		for(int j=1;j<=m;j++){
			if(pom[j]) continue;
			sorted.push_back({c[j],j});
		}
		sort(sorted.begin(),sorted.end());
		sort(aktz.begin(),aktz.end(),[](pair<int,int> a,pair<int,int> b){return a>b;});
		int wsk=sorted.size()-1;
		for(auto u:aktz){
			while(wsk>=0 and sorted[wsk].fi>=u.fi) Union(w[sorted[wsk].se].fi,w[sorted[wsk].se].se,0),wsk--;
			int ile=0;
			for(int j=u.se-1;j>=i;j--){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				pom2[zap[j].b]=1;
				if(zap[j].c>=u.fi) Union(w[zap[j].b].fi,w[zap[j].b].se,1);
			}	
			for(int j=u.se+1;j<=min(q,i+p-1);j++){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				if(c[zap[j].b]>=u.fi) ile++,Union(w[zap[j].b].fi,w[zap[j].b].se,1);
			}
			res[u.se]=siz[Find(zap[u.se].b)];
			rollback();
			for(int j=u.se-1;j>=i;j--) pom2[zap[j].b]=0;
		}
		for(int j=1;j<=n;j++) fau[j]=j,siz[j]=1;
		roolf.clear();
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) c[zap[j].b]=zap[j].c;
			pom[zap[j].b]=0;
		}
	}
	for(int i=1;i<=q;i++) if(zap[i].a==2) cout<<res[i]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 42 ms 516 KB Output is correct
4 Correct 26 ms 460 KB Output is correct
5 Correct 40 ms 504 KB Output is correct
6 Correct 35 ms 512 KB Output is correct
7 Correct 36 ms 460 KB Output is correct
8 Correct 38 ms 460 KB Output is correct
9 Correct 35 ms 460 KB Output is correct
10 Correct 40 ms 600 KB Output is correct
11 Correct 40 ms 480 KB Output is correct
12 Correct 41 ms 488 KB Output is correct
13 Correct 50 ms 460 KB Output is correct
14 Correct 45 ms 460 KB Output is correct
15 Correct 51 ms 580 KB Output is correct
16 Correct 38 ms 484 KB Output is correct
17 Correct 36 ms 460 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 3764 KB Output is correct
2 Correct 1320 ms 6616 KB Output is correct
3 Correct 1298 ms 6640 KB Output is correct
4 Correct 1464 ms 6660 KB Output is correct
5 Correct 1378 ms 6624 KB Output is correct
6 Correct 2015 ms 6372 KB Output is correct
7 Correct 2029 ms 6632 KB Output is correct
8 Correct 2011 ms 6484 KB Output is correct
9 Correct 268 ms 3400 KB Output is correct
10 Correct 1286 ms 5376 KB Output is correct
11 Correct 1256 ms 5444 KB Output is correct
12 Correct 1336 ms 6296 KB Output is correct
13 Correct 1145 ms 6592 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 3148 KB Output is correct
2 Correct 836 ms 3964 KB Output is correct
3 Correct 1296 ms 5304 KB Output is correct
4 Correct 1033 ms 5568 KB Output is correct
5 Correct 253 ms 3440 KB Output is correct
6 Correct 1196 ms 5512 KB Output is correct
7 Correct 1035 ms 5476 KB Output is correct
8 Correct 871 ms 5552 KB Output is correct
9 Correct 823 ms 5292 KB Output is correct
10 Correct 800 ms 5464 KB Output is correct
11 Correct 678 ms 5472 KB Output is correct
12 Correct 598 ms 5356 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 5460 KB Output is correct
2 Correct 258 ms 3400 KB Output is correct
3 Correct 163 ms 5304 KB Output is correct
4 Correct 151 ms 5448 KB Output is correct
5 Correct 1498 ms 7568 KB Output is correct
6 Correct 1567 ms 9120 KB Output is correct
7 Correct 1543 ms 7660 KB Output is correct
8 Correct 879 ms 6460 KB Output is correct
9 Correct 912 ms 6628 KB Output is correct
10 Correct 884 ms 6396 KB Output is correct
11 Correct 1272 ms 8072 KB Output is correct
12 Correct 1272 ms 8432 KB Output is correct
13 Correct 1269 ms 8088 KB Output is correct
14 Correct 1382 ms 7560 KB Output is correct
15 Correct 1439 ms 7596 KB Output is correct
16 Correct 1600 ms 9216 KB Output is correct
17 Correct 1598 ms 9148 KB Output is correct
18 Correct 1621 ms 9096 KB Output is correct
19 Correct 1575 ms 9128 KB Output is correct
20 Correct 1476 ms 8300 KB Output is correct
21 Correct 1380 ms 8072 KB Output is correct
22 Correct 1563 ms 8912 KB Output is correct
23 Correct 1464 ms 7096 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 3764 KB Output is correct
2 Correct 1320 ms 6616 KB Output is correct
3 Correct 1298 ms 6640 KB Output is correct
4 Correct 1464 ms 6660 KB Output is correct
5 Correct 1378 ms 6624 KB Output is correct
6 Correct 2015 ms 6372 KB Output is correct
7 Correct 2029 ms 6632 KB Output is correct
8 Correct 2011 ms 6484 KB Output is correct
9 Correct 268 ms 3400 KB Output is correct
10 Correct 1286 ms 5376 KB Output is correct
11 Correct 1256 ms 5444 KB Output is correct
12 Correct 1336 ms 6296 KB Output is correct
13 Correct 1145 ms 6592 KB Output is correct
14 Correct 1118 ms 3148 KB Output is correct
15 Correct 836 ms 3964 KB Output is correct
16 Correct 1296 ms 5304 KB Output is correct
17 Correct 1033 ms 5568 KB Output is correct
18 Correct 253 ms 3440 KB Output is correct
19 Correct 1196 ms 5512 KB Output is correct
20 Correct 1035 ms 5476 KB Output is correct
21 Correct 871 ms 5552 KB Output is correct
22 Correct 823 ms 5292 KB Output is correct
23 Correct 800 ms 5464 KB Output is correct
24 Correct 678 ms 5472 KB Output is correct
25 Correct 598 ms 5356 KB Output is correct
26 Correct 1422 ms 6812 KB Output is correct
27 Correct 1606 ms 6592 KB Output is correct
28 Correct 1410 ms 6592 KB Output is correct
29 Correct 1097 ms 6796 KB Output is correct
30 Correct 1760 ms 6556 KB Output is correct
31 Correct 1758 ms 6336 KB Output is correct
32 Correct 1713 ms 6608 KB Output is correct
33 Correct 1439 ms 6548 KB Output is correct
34 Correct 1398 ms 6640 KB Output is correct
35 Correct 1352 ms 6732 KB Output is correct
36 Correct 1118 ms 6552 KB Output is correct
37 Correct 1102 ms 6516 KB Output is correct
38 Correct 1094 ms 6864 KB Output is correct
39 Correct 1050 ms 6512 KB Output is correct
40 Correct 997 ms 6644 KB Output is correct
41 Correct 1065 ms 6716 KB Output is correct
42 Correct 793 ms 6444 KB Output is correct
43 Correct 792 ms 6424 KB Output is correct
44 Correct 761 ms 6572 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 42 ms 516 KB Output is correct
4 Correct 26 ms 460 KB Output is correct
5 Correct 40 ms 504 KB Output is correct
6 Correct 35 ms 512 KB Output is correct
7 Correct 36 ms 460 KB Output is correct
8 Correct 38 ms 460 KB Output is correct
9 Correct 35 ms 460 KB Output is correct
10 Correct 40 ms 600 KB Output is correct
11 Correct 40 ms 480 KB Output is correct
12 Correct 41 ms 488 KB Output is correct
13 Correct 50 ms 460 KB Output is correct
14 Correct 45 ms 460 KB Output is correct
15 Correct 51 ms 580 KB Output is correct
16 Correct 38 ms 484 KB Output is correct
17 Correct 36 ms 460 KB Output is correct
18 Correct 1286 ms 3764 KB Output is correct
19 Correct 1320 ms 6616 KB Output is correct
20 Correct 1298 ms 6640 KB Output is correct
21 Correct 1464 ms 6660 KB Output is correct
22 Correct 1378 ms 6624 KB Output is correct
23 Correct 2015 ms 6372 KB Output is correct
24 Correct 2029 ms 6632 KB Output is correct
25 Correct 2011 ms 6484 KB Output is correct
26 Correct 268 ms 3400 KB Output is correct
27 Correct 1286 ms 5376 KB Output is correct
28 Correct 1256 ms 5444 KB Output is correct
29 Correct 1336 ms 6296 KB Output is correct
30 Correct 1145 ms 6592 KB Output is correct
31 Correct 1118 ms 3148 KB Output is correct
32 Correct 836 ms 3964 KB Output is correct
33 Correct 1296 ms 5304 KB Output is correct
34 Correct 1033 ms 5568 KB Output is correct
35 Correct 253 ms 3440 KB Output is correct
36 Correct 1196 ms 5512 KB Output is correct
37 Correct 1035 ms 5476 KB Output is correct
38 Correct 871 ms 5552 KB Output is correct
39 Correct 823 ms 5292 KB Output is correct
40 Correct 800 ms 5464 KB Output is correct
41 Correct 678 ms 5472 KB Output is correct
42 Correct 598 ms 5356 KB Output is correct
43 Correct 1585 ms 5460 KB Output is correct
44 Correct 258 ms 3400 KB Output is correct
45 Correct 163 ms 5304 KB Output is correct
46 Correct 151 ms 5448 KB Output is correct
47 Correct 1498 ms 7568 KB Output is correct
48 Correct 1567 ms 9120 KB Output is correct
49 Correct 1543 ms 7660 KB Output is correct
50 Correct 879 ms 6460 KB Output is correct
51 Correct 912 ms 6628 KB Output is correct
52 Correct 884 ms 6396 KB Output is correct
53 Correct 1272 ms 8072 KB Output is correct
54 Correct 1272 ms 8432 KB Output is correct
55 Correct 1269 ms 8088 KB Output is correct
56 Correct 1382 ms 7560 KB Output is correct
57 Correct 1439 ms 7596 KB Output is correct
58 Correct 1600 ms 9216 KB Output is correct
59 Correct 1598 ms 9148 KB Output is correct
60 Correct 1621 ms 9096 KB Output is correct
61 Correct 1575 ms 9128 KB Output is correct
62 Correct 1476 ms 8300 KB Output is correct
63 Correct 1380 ms 8072 KB Output is correct
64 Correct 1563 ms 8912 KB Output is correct
65 Correct 1464 ms 7096 KB Output is correct
66 Correct 1422 ms 6812 KB Output is correct
67 Correct 1606 ms 6592 KB Output is correct
68 Correct 1410 ms 6592 KB Output is correct
69 Correct 1097 ms 6796 KB Output is correct
70 Correct 1760 ms 6556 KB Output is correct
71 Correct 1758 ms 6336 KB Output is correct
72 Correct 1713 ms 6608 KB Output is correct
73 Correct 1439 ms 6548 KB Output is correct
74 Correct 1398 ms 6640 KB Output is correct
75 Correct 1352 ms 6732 KB Output is correct
76 Correct 1118 ms 6552 KB Output is correct
77 Correct 1102 ms 6516 KB Output is correct
78 Correct 1094 ms 6864 KB Output is correct
79 Correct 1050 ms 6512 KB Output is correct
80 Correct 997 ms 6644 KB Output is correct
81 Correct 1065 ms 6716 KB Output is correct
82 Correct 793 ms 6444 KB Output is correct
83 Correct 792 ms 6424 KB Output is correct
84 Correct 761 ms 6572 KB Output is correct
85 Correct 1975 ms 9076 KB Output is correct
86 Correct 177 ms 5344 KB Output is correct
87 Correct 159 ms 5444 KB Output is correct
88 Correct 1822 ms 7564 KB Output is correct
89 Correct 1879 ms 9096 KB Output is correct
90 Correct 1828 ms 7652 KB Output is correct
91 Correct 1396 ms 6412 KB Output is correct
92 Correct 1425 ms 6832 KB Output is correct
93 Correct 2016 ms 6412 KB Output is correct
94 Correct 1683 ms 8012 KB Output is correct
95 Correct 1646 ms 8124 KB Output is correct
96 Correct 1941 ms 7904 KB Output is correct
97 Correct 1660 ms 7692 KB Output is correct
98 Correct 1557 ms 7652 KB Output is correct
99 Correct 1943 ms 8984 KB Output is correct
100 Correct 1938 ms 9324 KB Output is correct
101 Correct 1989 ms 9340 KB Output is correct
102 Correct 1942 ms 9068 KB Output is correct
103 Correct 2019 ms 8512 KB Output is correct
104 Correct 2011 ms 8372 KB Output is correct
105 Correct 1464 ms 8420 KB Output is correct
106 Correct 1219 ms 8124 KB Output is correct
107 Correct 1614 ms 8168 KB Output is correct
108 Correct 1968 ms 8880 KB Output is correct
109 Correct 1806 ms 7016 KB Output is correct