oj.uz

Submission #383047

# Submission time Handle Problem Language Result Execution time Memory
383047 2021-03-28T18:24:14 Z Kerim Bridges (APIO19_bridges) C++17
100 / 100
 2564 ms 108968 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=1000;
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(sz[x]<sz[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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 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 48 ms 748 KB Output is correct
4 Correct 13 ms 620 KB Output is correct
5 Correct 32 ms 656 KB Output is correct
6 Correct 30 ms 620 KB Output is correct
7 Correct 33 ms 620 KB Output is correct
8 Correct 31 ms 620 KB Output is correct
9 Correct 29 ms 620 KB Output is correct
10 Correct 32 ms 616 KB Output is correct
11 Correct 31 ms 620 KB Output is correct
12 Correct 32 ms 620 KB Output is correct
13 Correct 41 ms 620 KB Output is correct
14 Correct 38 ms 620 KB Output is correct
15 Correct 34 ms 620 KB Output is correct
16 Correct 31 ms 748 KB Output is correct
17 Correct 34 ms 620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 104888 KB Output is correct
2 Correct 1477 ms 104684 KB Output is correct
3 Correct 1463 ms 105248 KB Output is correct
4 Correct 1582 ms 104984 KB Output is correct
5 Correct 1593 ms 105128 KB Output is correct
6 Correct 2441 ms 104848 KB Output is correct
7 Correct 2338 ms 104840 KB Output is correct
8 Correct 2300 ms 105036 KB Output is correct
9 Correct 119 ms 2156 KB Output is correct
10 Correct 1345 ms 104968 KB Output is correct
11 Correct 1297 ms 104684 KB Output is correct
12 Correct 1281 ms 104684 KB Output is correct
13 Correct 1258 ms 104876 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 53892 KB Output is correct
2 Correct 965 ms 14980 KB Output is correct
3 Correct 1378 ms 54072 KB Output is correct
4 Correct 1155 ms 53808 KB Output is correct
5 Correct 118 ms 2156 KB Output is correct
6 Correct 1302 ms 53896 KB Output is correct
7 Correct 1079 ms 53800 KB Output is correct
8 Correct 978 ms 53800 KB Output is correct
9 Correct 762 ms 53808 KB Output is correct
10 Correct 668 ms 53944 KB Output is correct
11 Correct 750 ms 53804 KB Output is correct
12 Correct 652 ms 54092 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1452 ms 108492 KB Output is correct
2 Correct 120 ms 2156 KB Output is correct
3 Correct 190 ms 8696 KB Output is correct
4 Correct 116 ms 8440 KB Output is correct
5 Correct 1020 ms 108492 KB Output is correct
6 Correct 1473 ms 108752 KB Output is correct
7 Correct 1105 ms 108692 KB Output is correct
8 Correct 680 ms 104684 KB Output is correct
9 Correct 680 ms 104676 KB Output is correct
10 Correct 677 ms 104728 KB Output is correct
11 Correct 1111 ms 107104 KB Output is correct
12 Correct 1097 ms 107116 KB Output is correct
13 Correct 1109 ms 106964 KB Output is correct
14 Correct 913 ms 108788 KB Output is correct
15 Correct 1004 ms 108620 KB Output is correct
16 Correct 1442 ms 108496 KB Output is correct
17 Correct 1534 ms 108624 KB Output is correct
18 Correct 1571 ms 108464 KB Output is correct
19 Correct 1453 ms 108504 KB Output is correct
20 Correct 1273 ms 107636 KB Output is correct
21 Correct 1246 ms 107664 KB Output is correct
22 Correct 1399 ms 108588 KB Output is correct
23 Correct 1110 ms 107288 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 104888 KB Output is correct
2 Correct 1477 ms 104684 KB Output is correct
3 Correct 1463 ms 105248 KB Output is correct
4 Correct 1582 ms 104984 KB Output is correct
5 Correct 1593 ms 105128 KB Output is correct
6 Correct 2441 ms 104848 KB Output is correct
7 Correct 2338 ms 104840 KB Output is correct
8 Correct 2300 ms 105036 KB Output is correct
9 Correct 119 ms 2156 KB Output is correct
10 Correct 1345 ms 104968 KB Output is correct
11 Correct 1297 ms 104684 KB Output is correct
12 Correct 1281 ms 104684 KB Output is correct
13 Correct 1258 ms 104876 KB Output is correct
14 Correct 1192 ms 53892 KB Output is correct
15 Correct 965 ms 14980 KB Output is correct
16 Correct 1378 ms 54072 KB Output is correct
17 Correct 1155 ms 53808 KB Output is correct
18 Correct 118 ms 2156 KB Output is correct
19 Correct 1302 ms 53896 KB Output is correct
20 Correct 1079 ms 53800 KB Output is correct
21 Correct 978 ms 53800 KB Output is correct
22 Correct 762 ms 53808 KB Output is correct
23 Correct 668 ms 53944 KB Output is correct
24 Correct 750 ms 53804 KB Output is correct
25 Correct 652 ms 54092 KB Output is correct
26 Correct 1466 ms 104992 KB Output is correct
27 Correct 1902 ms 104684 KB Output is correct
28 Correct 1610 ms 104684 KB Output is correct
29 Correct 1229 ms 104940 KB Output is correct
30 Correct 1867 ms 104928 KB Output is correct
31 Correct 1870 ms 104748 KB Output is correct
32 Correct 1831 ms 104996 KB Output is correct
33 Correct 1513 ms 105012 KB Output is correct
34 Correct 1522 ms 104828 KB Output is correct
35 Correct 1539 ms 104812 KB Output is correct
36 Correct 1222 ms 105116 KB Output is correct
37 Correct 1207 ms 104812 KB Output is correct
38 Correct 1179 ms 104684 KB Output is correct
39 Correct 886 ms 104764 KB Output is correct
40 Correct 882 ms 104900 KB Output is correct
41 Correct 891 ms 104924 KB Output is correct
42 Correct 835 ms 104852 KB Output is correct
43 Correct 839 ms 104776 KB Output is correct
44 Correct 840 ms 104688 KB Output is correct

Subtask #6
27.0 / 27.0

# 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 48 ms 748 KB Output is correct
4 Correct 13 ms 620 KB Output is correct
5 Correct 32 ms 656 KB Output is correct
6 Correct 30 ms 620 KB Output is correct
7 Correct 33 ms 620 KB Output is correct
8 Correct 31 ms 620 KB Output is correct
9 Correct 29 ms 620 KB Output is correct
10 Correct 32 ms 616 KB Output is correct
11 Correct 31 ms 620 KB Output is correct
12 Correct 32 ms 620 KB Output is correct
13 Correct 41 ms 620 KB Output is correct
14 Correct 38 ms 620 KB Output is correct
15 Correct 34 ms 620 KB Output is correct
16 Correct 31 ms 748 KB Output is correct
17 Correct 34 ms 620 KB Output is correct
18 Correct 1472 ms 104888 KB Output is correct
19 Correct 1477 ms 104684 KB Output is correct
20 Correct 1463 ms 105248 KB Output is correct
21 Correct 1582 ms 104984 KB Output is correct
22 Correct 1593 ms 105128 KB Output is correct
23 Correct 2441 ms 104848 KB Output is correct
24 Correct 2338 ms 104840 KB Output is correct
25 Correct 2300 ms 105036 KB Output is correct
26 Correct 119 ms 2156 KB Output is correct
27 Correct 1345 ms 104968 KB Output is correct
28 Correct 1297 ms 104684 KB Output is correct
29 Correct 1281 ms 104684 KB Output is correct
30 Correct 1258 ms 104876 KB Output is correct
31 Correct 1192 ms 53892 KB Output is correct
32 Correct 965 ms 14980 KB Output is correct
33 Correct 1378 ms 54072 KB Output is correct
34 Correct 1155 ms 53808 KB Output is correct
35 Correct 118 ms 2156 KB Output is correct
36 Correct 1302 ms 53896 KB Output is correct
37 Correct 1079 ms 53800 KB Output is correct
38 Correct 978 ms 53800 KB Output is correct
39 Correct 762 ms 53808 KB Output is correct
40 Correct 668 ms 53944 KB Output is correct
41 Correct 750 ms 53804 KB Output is correct
42 Correct 652 ms 54092 KB Output is correct
43 Correct 1452 ms 108492 KB Output is correct
44 Correct 120 ms 2156 KB Output is correct
45 Correct 190 ms 8696 KB Output is correct
46 Correct 116 ms 8440 KB Output is correct
47 Correct 1020 ms 108492 KB Output is correct
48 Correct 1473 ms 108752 KB Output is correct
49 Correct 1105 ms 108692 KB Output is correct
50 Correct 680 ms 104684 KB Output is correct
51 Correct 680 ms 104676 KB Output is correct
52 Correct 677 ms 104728 KB Output is correct
53 Correct 1111 ms 107104 KB Output is correct
54 Correct 1097 ms 107116 KB Output is correct
55 Correct 1109 ms 106964 KB Output is correct
56 Correct 913 ms 108788 KB Output is correct
57 Correct 1004 ms 108620 KB Output is correct
58 Correct 1442 ms 108496 KB Output is correct
59 Correct 1534 ms 108624 KB Output is correct
60 Correct 1571 ms 108464 KB Output is correct
61 Correct 1453 ms 108504 KB Output is correct
62 Correct 1273 ms 107636 KB Output is correct
63 Correct 1246 ms 107664 KB Output is correct
64 Correct 1399 ms 108588 KB Output is correct
65 Correct 1110 ms 107288 KB Output is correct
66 Correct 1466 ms 104992 KB Output is correct
67 Correct 1902 ms 104684 KB Output is correct
68 Correct 1610 ms 104684 KB Output is correct
69 Correct 1229 ms 104940 KB Output is correct
70 Correct 1867 ms 104928 KB Output is correct
71 Correct 1870 ms 104748 KB Output is correct
72 Correct 1831 ms 104996 KB Output is correct
73 Correct 1513 ms 105012 KB Output is correct
74 Correct 1522 ms 104828 KB Output is correct
75 Correct 1539 ms 104812 KB Output is correct
76 Correct 1222 ms 105116 KB Output is correct
77 Correct 1207 ms 104812 KB Output is correct
78 Correct 1179 ms 104684 KB Output is correct
79 Correct 886 ms 104764 KB Output is correct
80 Correct 882 ms 104900 KB Output is correct
81 Correct 891 ms 104924 KB Output is correct
82 Correct 835 ms 104852 KB Output is correct
83 Correct 839 ms 104776 KB Output is correct
84 Correct 840 ms 104688 KB Output is correct
85 Correct 2160 ms 108804 KB Output is correct
86 Correct 240 ms 8476 KB Output is correct
87 Correct 181 ms 8428 KB Output is correct
88 Correct 1729 ms 108624 KB Output is correct
89 Correct 2171 ms 108956 KB Output is correct
90 Correct 1746 ms 108968 KB Output is correct
91 Correct 1625 ms 104872 KB Output is correct
92 Correct 1635 ms 104968 KB Output is correct
93 Correct 2271 ms 104840 KB Output is correct
94 Correct 1992 ms 107104 KB Output is correct
95 Correct 1929 ms 107220 KB Output is correct
96 Correct 2307 ms 106980 KB Output is correct
97 Correct 1290 ms 108748 KB Output is correct
98 Correct 1297 ms 108652 KB Output is correct
99 Correct 2231 ms 108640 KB Output is correct
100 Correct 2218 ms 108636 KB Output is correct
101 Correct 2395 ms 108680 KB Output is correct
102 Correct 2358 ms 108624 KB Output is correct
103 Correct 2564 ms 107436 KB Output is correct
104 Correct 2518 ms 107692 KB Output is correct
105 Correct 1933 ms 107712 KB Output is correct
106 Correct 1428 ms 107240 KB Output is correct
107 Correct 1748 ms 107680 KB Output is correct
108 Correct 2449 ms 108676 KB Output is correct
109 Correct 2068 ms 107644 KB Output is correct