oj.uz

Submission #252743

# Submission time Handle Problem Language Result Execution time Memory
252743 2020-07-26T08:10:33 Z kshitij_sodani Bridges (APIO19_bridges) C++14
100 / 100
 2482 ms 28044 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
vector<pair<pair<int,int>,pair<int,int>>> ed;
vector<pair<pair<int,int>,pair<int,int>>> ed2;
vector<pair<pair<int,int>,pair<int,int>>> ed3;
vector<pair<pair<int,int>,pair<int,int>>> ed4;

int n,m,q;
vector<pair<int,pair<int,int>>> qq;
const int ss=600;
vector<int> kk;
vector<int> mm;
int vis[100001];
int par[50001];
int tt[50001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int ans[100001];
int vis2[100001];
vector<int> adj[50001];
int val[100001];
int vis3[100001];
int cot=0;
void dfs(int no){
	vis3[no]=1;
	cot+=tt[no];
	for(auto j:adj[no]){
		if(vis3[j]==0){
			dfs(j);
		}
	}
}
int vis4[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ed2.pb({{cc,i},{aa,bb}});
		val[i]=cc;
	}
	/*sort(cc.begin(),cc.end());
	reverse(cc.begin(),cc.end());*/
	cin>>q;
	for(int i=0;i<q;i++){
		int t;
		cin>>t;
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		qq.pb({t,{aa,bb}});
	}
	ed=ed2;
	sort(ed.begin(),ed.end());
	reverse(ed.begin(),ed.end());

	set<int> rep;
	for(int i=0;i<=(q-1)/ss;i++){
		//cout<<i<<":::"<<endl;
		vector<pair<pair<int,int>,int>> cur;
		for(auto j:rep){
			vis4[j]=1;
			ed3.pb({{val[j],j},ed2[j].b});
		}
		sort(ed3.begin(),ed3.end());
		reverse(ed3.begin(),ed3.end());
		int ind3=0;
		int ind4=0;
		while(ind3<ed3.size() or ind4<ed.size()){
			int st=1;
			if(ind3==ed3.size()){
				st=0;
			}
			else if(ind4==ed.size()){

			}
			else{
				if(ed[ind4].a.a>=ed3[ind3].a.a){
					st=0;
				}
			}
			if(st){
				ed4.pb(ed3[ind3]);
				ind3++;
			}
			else{
				if(vis4[ed[ind4].a.b]==0){
					ed4.pb(ed[ind4]);
				}
				ind4++;
			}
		}



		ed3.clear();
		for(auto j:rep){
			vis4[j]=0;
		}
		ed=ed4;
		ed4.clear();
		/*ed.clear();*/
		/*for(int j=0;j<m;j++){
			ed.pb({{val[ed2[j].a.b],ed2[j].a.b},ed2[j].b});
		}*/
		/*sort(ed.begin(),ed.end());
		reverse(ed.begin(),ed.end());
*/
		for(int j=ss*i;j<min(ss*(i+1),q);j++){
			if(qq[j].a==1){
				vis[qq[j].b.a]=1;
				kk.pb(qq[j].b.a);
			//	cout<<qq[j].b.a<<endl;
			}
			else{
				cur.pb({{qq[j].b.b,qq[j].b.a},j});
			}
		}

		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		for(int j=0;j<n;j++){
			par[j]=j;
			tt[j]=1;
		}
		int ind=0;
		int ind2=0;
		while(ind<cur.size() or ind2<ed.size()){
			int st=1;//1 denotes take cur
			if(ind==cur.size()){
				st=0;
			}
			else if(ind2==ed.size()){
			}
			else{
				if(ed[ind2].a.a>=cur[ind].a.a){
					st=0;
				}
			}
			if(st){
				//take cur
				vector<int> nn;
				for(int j=cur[ind].b;j>=ss*i;j--){
					if(qq[j].a==1){
						if(vis2[qq[j].b.a]==0){
							mm.pb(qq[j].b.a);
							vis2[qq[j].b.a]=1;
							if(qq[j].b.b>=cur[ind].a.a){
								int x=find(ed2[qq[j].b.a].b.a);
								int y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				for(int j=cur[ind].b;j<min(ss*(i+1),q);j++){
					if(qq[j].a==1){
						if(vis2[qq[j].b.a]==0){
							mm.pb(qq[j].b.a);
							vis2[qq[j].b.a]=1;
							if(val[qq[j].b.a]>=cur[ind].a.a){
								int x=find(ed2[qq[j].b.a].b.a);
								int y=find(ed2[qq[j].b.a].b.b);
								adj[x].pb(y);
								adj[y].pb(x);
							//	cout<<x<<"//"<<y<<endl;
								nn.pb(x);
								nn.pb(y);
							}
						}
					}
				}
				int xx=find(cur[ind].a.b);
			//	cout<<xx<<endl;
				cot=0;
			//	cout<<cur[ind].b<<"/"<<endl;
				dfs(xx);
				ans[cur[ind].b]=cot;

				for(auto j:nn){
					vis3[j]=0;
					adj[j].clear();
				}
				vis3[xx]=0;
				for(auto j:mm){
					vis2[j]=0;
				}
				nn.clear();
				mm.clear();
				ind++;
			}
			else{
				//add edge
			///	cout<<1<<":"<<ed[ind2].a.a<<","<<ed[ind2].a.b<<","<<ed[ind2].b.a<<","<<ed[ind2].b.b<<endl;
				if(vis[ed[ind2].a.b]){
				}
				else{
					int x=find(ed[ind2].b.a);
					int y=find(ed[ind2].b.b);
				//	cout<<ed[ind2].b.b<<":"<<ed[ind2].b.a<<endl;
					if(x!=y){
						par[y]=x;
						tt[x]+=tt[y];
					}
				}
				ind2++;
			}
		}
		for(auto j:kk){
			vis[j]=0;
		}
		kk.clear();

		rep.clear();
		for(int j=ss*i;j<min(ss*(i+1),q);j++){
			if(qq[j].a==1){
				val[qq[j].b.a]=qq[j].b.b;
				rep.insert(qq[j].b.a);
			}
		}
	}
	for(int i=0;i<q;i++){
		if(qq[i].a==2){
			cout<<ans[i]<<endl;
		}
	}






	return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:83:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind3<ed3.size() or ind4<ed.size()){
         ~~~~^~~~~~~~~~~
bridges.cpp:83:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind3<ed3.size() or ind4<ed.size()){
                            ~~~~^~~~~~~~~~
bridges.cpp:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind3==ed3.size()){
       ~~~~^~~~~~~~~~~~
bridges.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(ind4==ed.size()){
            ~~~~^~~~~~~~~~~
bridges.cpp:142:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
         ~~~^~~~~~~~~~~
bridges.cpp:142:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() or ind2<ed.size()){
                           ~~~~^~~~~~~~~~
bridges.cpp:144:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind==cur.size()){
       ~~~^~~~~~~~~~~~
bridges.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(ind2==ed.size()){
            ~~~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 64 ms 1868 KB Output is correct
4 Correct 29 ms 1856 KB Output is correct
5 Correct 42 ms 1856 KB Output is correct
6 Correct 43 ms 1856 KB Output is correct
7 Correct 45 ms 1976 KB Output is correct
8 Correct 40 ms 1856 KB Output is correct
9 Correct 52 ms 1856 KB Output is correct
10 Correct 41 ms 1856 KB Output is correct
11 Correct 40 ms 1856 KB Output is correct
12 Correct 43 ms 1856 KB Output is correct
13 Correct 50 ms 1860 KB Output is correct
14 Correct 46 ms 1860 KB Output is correct
15 Correct 45 ms 1860 KB Output is correct
16 Correct 44 ms 1856 KB Output is correct
17 Correct 46 ms 1856 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1290 ms 8300 KB Output is correct
2 Correct 1257 ms 8300 KB Output is correct
3 Correct 1317 ms 8344 KB Output is correct
4 Correct 1252 ms 8556 KB Output is correct
5 Correct 1243 ms 8420 KB Output is correct
6 Correct 1793 ms 8432 KB Output is correct
7 Correct 1685 ms 8452 KB Output is correct
8 Correct 1663 ms 8164 KB Output is correct
9 Correct 286 ms 3432 KB Output is correct
10 Correct 1488 ms 8556 KB Output is correct
11 Correct 1363 ms 8292 KB Output is correct
12 Correct 1012 ms 8428 KB Output is correct
13 Correct 867 ms 8260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 6748 KB Output is correct
2 Correct 1108 ms 4324 KB Output is correct
3 Correct 1375 ms 6768 KB Output is correct
4 Correct 1095 ms 6764 KB Output is correct
5 Correct 276 ms 3416 KB Output is correct
6 Correct 1206 ms 6932 KB Output is correct
7 Correct 1031 ms 6792 KB Output is correct
8 Correct 907 ms 6764 KB Output is correct
9 Correct 792 ms 6380 KB Output is correct
10 Correct 736 ms 6376 KB Output is correct
11 Correct 639 ms 6632 KB Output is correct
12 Correct 543 ms 6912 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1569 ms 9512 KB Output is correct
2 Correct 266 ms 3432 KB Output is correct
3 Correct 104 ms 8940 KB Output is correct
4 Correct 104 ms 8936 KB Output is correct
5 Correct 1508 ms 9444 KB Output is correct
6 Correct 1577 ms 9412 KB Output is correct
7 Correct 1507 ms 9728 KB Output is correct
8 Correct 664 ms 7532 KB Output is correct
9 Correct 652 ms 7520 KB Output is correct
10 Correct 640 ms 7916 KB Output is correct
11 Correct 988 ms 8424 KB Output is correct
12 Correct 959 ms 8424 KB Output is correct
13 Correct 977 ms 8424 KB Output is correct
14 Correct 1474 ms 9572 KB Output is correct
15 Correct 1476 ms 9444 KB Output is correct
16 Correct 1461 ms 9320 KB Output is correct
17 Correct 1472 ms 9412 KB Output is correct
18 Correct 1392 ms 9572 KB Output is correct
19 Correct 1395 ms 9356 KB Output is correct
20 Correct 1134 ms 8776 KB Output is correct
21 Correct 1126 ms 8680 KB Output is correct
22 Correct 1457 ms 9312 KB Output is correct
23 Correct 1179 ms 8552 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1290 ms 8300 KB Output is correct
2 Correct 1257 ms 8300 KB Output is correct
3 Correct 1317 ms 8344 KB Output is correct
4 Correct 1252 ms 8556 KB Output is correct
5 Correct 1243 ms 8420 KB Output is correct
6 Correct 1793 ms 8432 KB Output is correct
7 Correct 1685 ms 8452 KB Output is correct
8 Correct 1663 ms 8164 KB Output is correct
9 Correct 286 ms 3432 KB Output is correct
10 Correct 1488 ms 8556 KB Output is correct
11 Correct 1363 ms 8292 KB Output is correct
12 Correct 1012 ms 8428 KB Output is correct
13 Correct 867 ms 8260 KB Output is correct
14 Correct 1118 ms 6748 KB Output is correct
15 Correct 1108 ms 4324 KB Output is correct
16 Correct 1375 ms 6768 KB Output is correct
17 Correct 1095 ms 6764 KB Output is correct
18 Correct 276 ms 3416 KB Output is correct
19 Correct 1206 ms 6932 KB Output is correct
20 Correct 1031 ms 6792 KB Output is correct
21 Correct 907 ms 6764 KB Output is correct
22 Correct 792 ms 6380 KB Output is correct
23 Correct 736 ms 6376 KB Output is correct
24 Correct 639 ms 6632 KB Output is correct
25 Correct 543 ms 6912 KB Output is correct
26 Correct 1243 ms 8580 KB Output is correct
27 Correct 1787 ms 11116 KB Output is correct
28 Correct 1611 ms 15736 KB Output is correct
29 Correct 1247 ms 10664 KB Output is correct
30 Correct 1599 ms 8576 KB Output is correct
31 Correct 1671 ms 8716 KB Output is correct
32 Correct 1667 ms 8544 KB Output is correct
33 Correct 1400 ms 8420 KB Output is correct
34 Correct 1434 ms 8404 KB Output is correct
35 Correct 1500 ms 8576 KB Output is correct
36 Correct 1099 ms 8468 KB Output is correct
37 Correct 1099 ms 8476 KB Output is correct
38 Correct 1086 ms 8328 KB Output is correct
39 Correct 864 ms 8076 KB Output is correct
40 Correct 879 ms 8036 KB Output is correct
41 Correct 889 ms 8036 KB Output is correct
42 Correct 744 ms 8424 KB Output is correct
43 Correct 719 ms 8552 KB Output is correct
44 Correct 727 ms 8400 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 64 ms 1868 KB Output is correct
4 Correct 29 ms 1856 KB Output is correct
5 Correct 42 ms 1856 KB Output is correct
6 Correct 43 ms 1856 KB Output is correct
7 Correct 45 ms 1976 KB Output is correct
8 Correct 40 ms 1856 KB Output is correct
9 Correct 52 ms 1856 KB Output is correct
10 Correct 41 ms 1856 KB Output is correct
11 Correct 40 ms 1856 KB Output is correct
12 Correct 43 ms 1856 KB Output is correct
13 Correct 50 ms 1860 KB Output is correct
14 Correct 46 ms 1860 KB Output is correct
15 Correct 45 ms 1860 KB Output is correct
16 Correct 44 ms 1856 KB Output is correct
17 Correct 46 ms 1856 KB Output is correct
18 Correct 1290 ms 8300 KB Output is correct
19 Correct 1257 ms 8300 KB Output is correct
20 Correct 1317 ms 8344 KB Output is correct
21 Correct 1252 ms 8556 KB Output is correct
22 Correct 1243 ms 8420 KB Output is correct
23 Correct 1793 ms 8432 KB Output is correct
24 Correct 1685 ms 8452 KB Output is correct
25 Correct 1663 ms 8164 KB Output is correct
26 Correct 286 ms 3432 KB Output is correct
27 Correct 1488 ms 8556 KB Output is correct
28 Correct 1363 ms 8292 KB Output is correct
29 Correct 1012 ms 8428 KB Output is correct
30 Correct 867 ms 8260 KB Output is correct
31 Correct 1118 ms 6748 KB Output is correct
32 Correct 1108 ms 4324 KB Output is correct
33 Correct 1375 ms 6768 KB Output is correct
34 Correct 1095 ms 6764 KB Output is correct
35 Correct 276 ms 3416 KB Output is correct
36 Correct 1206 ms 6932 KB Output is correct
37 Correct 1031 ms 6792 KB Output is correct
38 Correct 907 ms 6764 KB Output is correct
39 Correct 792 ms 6380 KB Output is correct
40 Correct 736 ms 6376 KB Output is correct
41 Correct 639 ms 6632 KB Output is correct
42 Correct 543 ms 6912 KB Output is correct
43 Correct 1569 ms 9512 KB Output is correct
44 Correct 266 ms 3432 KB Output is correct
45 Correct 104 ms 8940 KB Output is correct
46 Correct 104 ms 8936 KB Output is correct
47 Correct 1508 ms 9444 KB Output is correct
48 Correct 1577 ms 9412 KB Output is correct
49 Correct 1507 ms 9728 KB Output is correct
50 Correct 664 ms 7532 KB Output is correct
51 Correct 652 ms 7520 KB Output is correct
52 Correct 640 ms 7916 KB Output is correct
53 Correct 988 ms 8424 KB Output is correct
54 Correct 959 ms 8424 KB Output is correct
55 Correct 977 ms 8424 KB Output is correct
56 Correct 1474 ms 9572 KB Output is correct
57 Correct 1476 ms 9444 KB Output is correct
58 Correct 1461 ms 9320 KB Output is correct
59 Correct 1472 ms 9412 KB Output is correct
60 Correct 1392 ms 9572 KB Output is correct
61 Correct 1395 ms 9356 KB Output is correct
62 Correct 1134 ms 8776 KB Output is correct
63 Correct 1126 ms 8680 KB Output is correct
64 Correct 1457 ms 9312 KB Output is correct
65 Correct 1179 ms 8552 KB Output is correct
66 Correct 1243 ms 8580 KB Output is correct
67 Correct 1787 ms 11116 KB Output is correct
68 Correct 1611 ms 15736 KB Output is correct
69 Correct 1247 ms 10664 KB Output is correct
70 Correct 1599 ms 8576 KB Output is correct
71 Correct 1671 ms 8716 KB Output is correct
72 Correct 1667 ms 8544 KB Output is correct
73 Correct 1400 ms 8420 KB Output is correct
74 Correct 1434 ms 8404 KB Output is correct
75 Correct 1500 ms 8576 KB Output is correct
76 Correct 1099 ms 8468 KB Output is correct
77 Correct 1099 ms 8476 KB Output is correct
78 Correct 1086 ms 8328 KB Output is correct
79 Correct 864 ms 8076 KB Output is correct
80 Correct 879 ms 8036 KB Output is correct
81 Correct 889 ms 8036 KB Output is correct
82 Correct 744 ms 8424 KB Output is correct
83 Correct 719 ms 8552 KB Output is correct
84 Correct 727 ms 8400 KB Output is correct
85 Correct 2475 ms 24300 KB Output is correct
86 Correct 152 ms 12008 KB Output is correct
87 Correct 173 ms 12136 KB Output is correct
88 Correct 2207 ms 14520 KB Output is correct
89 Correct 2482 ms 28044 KB Output is correct
90 Correct 2132 ms 13900 KB Output is correct
91 Correct 1342 ms 10988 KB Output is correct
92 Correct 1323 ms 11412 KB Output is correct
93 Correct 1674 ms 10940 KB Output is correct
94 Correct 1681 ms 13556 KB Output is correct
95 Correct 1672 ms 14044 KB Output is correct
96 Correct 1862 ms 12188 KB Output is correct
97 Correct 1806 ms 12588 KB Output is correct
98 Correct 1627 ms 14788 KB Output is correct
99 Correct 2447 ms 26924 KB Output is correct
100 Correct 2352 ms 26532 KB Output is correct
101 Correct 2266 ms 22896 KB Output is correct
102 Correct 2332 ms 23344 KB Output is correct
103 Correct 1964 ms 12464 KB Output is correct
104 Correct 1964 ms 12404 KB Output is correct
105 Correct 1284 ms 12568 KB Output is correct
106 Correct 978 ms 12256 KB Output is correct
107 Correct 1472 ms 12532 KB Output is correct
108 Correct 2480 ms 20784 KB Output is correct
109 Correct 1992 ms 11292 KB Output is correct