oj.uz

Submission #484907

# Submission time Handle Problem Language Result Execution time Memory
484907 2021-11-05T17:46:42 Z MilosMilutinovic Bridges (APIO19_bridges) C++14
100 / 100
 2739 ms 192148 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int BLOCK=900;
int n,m,q,u[N],v[N],w[N],t[N],x[N],y[N],ans[N];
vector<int> qs[BLOCK+5];
bool vis[N];
struct Dsu{
	int p[N],sz[N];
	void init(){
		for(int i=1;i<=n;i++){
			p[i]=i;
			sz[i]=1;
		}
	}
	int root(int u){
		return p[u]==u?u:root(p[u]);
	}
	stack<tuple<int,int,int,int>> stk;
	void unite(int u,int v){
		u=root(u);
		v=root(v);
		if(sz[u]<sz[v])swap(u,v);
		stk.push({u,v,sz[u],sz[v]});
		if(u==v)return;
		p[v]=u;
		sz[u]+=sz[v];
	}
	void rollback(){
		auto op=stk.top();
		stk.pop();
		int u=get<0>(op);
		int v=get<1>(op);
		p[u]=u;
		p[v]=v;
		sz[u]=get<2>(op);
		sz[v]=get<3>(op);
	}
}d;
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	}
	for(int l=1;l<=q;l+=BLOCK){
		int r=min(q,l+BLOCK-1);
		for(int i=0;i<=BLOCK;i++)qs[i].clear();
		for(int id=1;id<=m;id++)vis[id]=false;
		d.init();
		vector<int> edg,ver;
		for(int i=l;i<=r;i++)if(t[i]==1)edg.push_back(x[i]);
		for(int i=l;i<=r;i++){
			if(t[i]==1){
				vis[x[i]]=true;
				w[x[i]]=y[i];
			}else{
				for(int id:edg)if(w[id]>=y[i])qs[i-l].push_back(id);
				ver.push_back(i);
			}
		}
		vector<int> unu;
		for(int id=1;id<=m;id++)if(!vis[id])unu.push_back(id);
		sort(ver.begin(),ver.end(),[&](int i,int j){
			return y[i]>y[j];
		});
		sort(unu.begin(),unu.end(),[&](int i,int j){
			return w[i]>w[j];
		});
		int ptr=0;
		for(int i=0;i<(int)ver.size();i++){
			int pos=ver[i],bd=pos-l;
			while (ptr<unu.size()&&y[pos]<=w[unu[ptr]]){
				d.unite(u[unu[ptr]],v[unu[ptr]]);
				ptr++;
			}
			for(int id:qs[bd])d.unite(u[id],v[id]);
			ans[pos]=d.sz[d.root(x[pos])];
			for(int id:qs[bd])d.rollback();
		}
	}
	for(int i=1;i<=q;i++){
		if(t[i]==2){
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    while (ptr<unu.size()&&y[pos]<=w[unu[ptr]]){
      |           ~~~^~~~~~~~~~~
bridges.cpp:82:12: warning: unused variable 'id' [-Wunused-variable]
   82 |    for(int id:qs[bd])d.rollback();
      |            ^~
bridges.cpp:41:7: 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:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d%d",&u[i],&v[i],&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
bridges.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d%d%d",&t[i],&x[i],&y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 43 ms 2436 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 47 ms 2416 KB Output is correct
6 Correct 41 ms 2120 KB Output is correct
7 Correct 47 ms 2356 KB Output is correct
8 Correct 47 ms 2332 KB Output is correct
9 Correct 52 ms 2320 KB Output is correct
10 Correct 48 ms 2352 KB Output is correct
11 Correct 49 ms 2312 KB Output is correct
12 Correct 57 ms 2336 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 48 ms 2356 KB Output is correct
15 Correct 54 ms 2320 KB Output is correct
16 Correct 51 ms 2412 KB Output is correct
17 Correct 59 ms 2332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 95796 KB Output is correct
2 Correct 1370 ms 95892 KB Output is correct
3 Correct 1337 ms 95916 KB Output is correct
4 Correct 1379 ms 95932 KB Output is correct
5 Correct 1420 ms 95824 KB Output is correct
6 Correct 1919 ms 96188 KB Output is correct
7 Correct 1945 ms 96108 KB Output is correct
8 Correct 1948 ms 96148 KB Output is correct
9 Correct 35 ms 2064 KB Output is correct
10 Correct 1055 ms 96232 KB Output is correct
11 Correct 1000 ms 96180 KB Output is correct
12 Correct 1216 ms 95764 KB Output is correct
13 Correct 1232 ms 97040 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 63908 KB Output is correct
2 Correct 714 ms 18324 KB Output is correct
3 Correct 1222 ms 64040 KB Output is correct
4 Correct 1082 ms 63936 KB Output is correct
5 Correct 51 ms 1988 KB Output is correct
6 Correct 1192 ms 63988 KB Output is correct
7 Correct 941 ms 63868 KB Output is correct
8 Correct 829 ms 63708 KB Output is correct
9 Correct 746 ms 63532 KB Output is correct
10 Correct 662 ms 63428 KB Output is correct
11 Correct 763 ms 64736 KB Output is correct
12 Correct 652 ms 64580 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 187764 KB Output is correct
2 Correct 39 ms 1996 KB Output is correct
3 Correct 181 ms 21688 KB Output is correct
4 Correct 90 ms 21712 KB Output is correct
5 Correct 1018 ms 187964 KB Output is correct
6 Correct 1755 ms 187744 KB Output is correct
7 Correct 968 ms 187992 KB Output is correct
8 Correct 858 ms 95072 KB Output is correct
9 Correct 875 ms 94996 KB Output is correct
10 Correct 840 ms 95276 KB Output is correct
11 Correct 1321 ms 141372 KB Output is correct
12 Correct 1422 ms 141396 KB Output is correct
13 Correct 1384 ms 141684 KB Output is correct
14 Correct 864 ms 188076 KB Output is correct
15 Correct 923 ms 188008 KB Output is correct
16 Correct 1748 ms 186088 KB Output is correct
17 Correct 1849 ms 185876 KB Output is correct
18 Correct 1821 ms 186552 KB Output is correct
19 Correct 1839 ms 186184 KB Output is correct
20 Correct 1611 ms 157172 KB Output is correct
21 Correct 1616 ms 157200 KB Output is correct
22 Correct 1784 ms 178904 KB Output is correct
23 Correct 1102 ms 151308 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 95796 KB Output is correct
2 Correct 1370 ms 95892 KB Output is correct
3 Correct 1337 ms 95916 KB Output is correct
4 Correct 1379 ms 95932 KB Output is correct
5 Correct 1420 ms 95824 KB Output is correct
6 Correct 1919 ms 96188 KB Output is correct
7 Correct 1945 ms 96108 KB Output is correct
8 Correct 1948 ms 96148 KB Output is correct
9 Correct 35 ms 2064 KB Output is correct
10 Correct 1055 ms 96232 KB Output is correct
11 Correct 1000 ms 96180 KB Output is correct
12 Correct 1216 ms 95764 KB Output is correct
13 Correct 1232 ms 97040 KB Output is correct
14 Correct 1077 ms 63908 KB Output is correct
15 Correct 714 ms 18324 KB Output is correct
16 Correct 1222 ms 64040 KB Output is correct
17 Correct 1082 ms 63936 KB Output is correct
18 Correct 51 ms 1988 KB Output is correct
19 Correct 1192 ms 63988 KB Output is correct
20 Correct 941 ms 63868 KB Output is correct
21 Correct 829 ms 63708 KB Output is correct
22 Correct 746 ms 63532 KB Output is correct
23 Correct 662 ms 63428 KB Output is correct
24 Correct 763 ms 64736 KB Output is correct
25 Correct 652 ms 64580 KB Output is correct
26 Correct 1391 ms 95824 KB Output is correct
27 Correct 1730 ms 96128 KB Output is correct
28 Correct 1481 ms 95924 KB Output is correct
29 Correct 1102 ms 95432 KB Output is correct
30 Correct 1661 ms 96112 KB Output is correct
31 Correct 1657 ms 96064 KB Output is correct
32 Correct 1681 ms 96056 KB Output is correct
33 Correct 1412 ms 95916 KB Output is correct
34 Correct 1506 ms 95836 KB Output is correct
35 Correct 1444 ms 95900 KB Output is correct
36 Correct 1123 ms 95616 KB Output is correct
37 Correct 1131 ms 95524 KB Output is correct
38 Correct 1205 ms 95528 KB Output is correct
39 Correct 1018 ms 95232 KB Output is correct
40 Correct 980 ms 95152 KB Output is correct
41 Correct 992 ms 95024 KB Output is correct
42 Correct 988 ms 93316 KB Output is correct
43 Correct 1047 ms 93328 KB Output is correct
44 Correct 950 ms 92820 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 0 ms 332 KB Output is correct
3 Correct 43 ms 2436 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 47 ms 2416 KB Output is correct
6 Correct 41 ms 2120 KB Output is correct
7 Correct 47 ms 2356 KB Output is correct
8 Correct 47 ms 2332 KB Output is correct
9 Correct 52 ms 2320 KB Output is correct
10 Correct 48 ms 2352 KB Output is correct
11 Correct 49 ms 2312 KB Output is correct
12 Correct 57 ms 2336 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 48 ms 2356 KB Output is correct
15 Correct 54 ms 2320 KB Output is correct
16 Correct 51 ms 2412 KB Output is correct
17 Correct 59 ms 2332 KB Output is correct
18 Correct 1342 ms 95796 KB Output is correct
19 Correct 1370 ms 95892 KB Output is correct
20 Correct 1337 ms 95916 KB Output is correct
21 Correct 1379 ms 95932 KB Output is correct
22 Correct 1420 ms 95824 KB Output is correct
23 Correct 1919 ms 96188 KB Output is correct
24 Correct 1945 ms 96108 KB Output is correct
25 Correct 1948 ms 96148 KB Output is correct
26 Correct 35 ms 2064 KB Output is correct
27 Correct 1055 ms 96232 KB Output is correct
28 Correct 1000 ms 96180 KB Output is correct
29 Correct 1216 ms 95764 KB Output is correct
30 Correct 1232 ms 97040 KB Output is correct
31 Correct 1077 ms 63908 KB Output is correct
32 Correct 714 ms 18324 KB Output is correct
33 Correct 1222 ms 64040 KB Output is correct
34 Correct 1082 ms 63936 KB Output is correct
35 Correct 51 ms 1988 KB Output is correct
36 Correct 1192 ms 63988 KB Output is correct
37 Correct 941 ms 63868 KB Output is correct
38 Correct 829 ms 63708 KB Output is correct
39 Correct 746 ms 63532 KB Output is correct
40 Correct 662 ms 63428 KB Output is correct
41 Correct 763 ms 64736 KB Output is correct
42 Correct 652 ms 64580 KB Output is correct
43 Correct 1836 ms 187764 KB Output is correct
44 Correct 39 ms 1996 KB Output is correct
45 Correct 181 ms 21688 KB Output is correct
46 Correct 90 ms 21712 KB Output is correct
47 Correct 1018 ms 187964 KB Output is correct
48 Correct 1755 ms 187744 KB Output is correct
49 Correct 968 ms 187992 KB Output is correct
50 Correct 858 ms 95072 KB Output is correct
51 Correct 875 ms 94996 KB Output is correct
52 Correct 840 ms 95276 KB Output is correct
53 Correct 1321 ms 141372 KB Output is correct
54 Correct 1422 ms 141396 KB Output is correct
55 Correct 1384 ms 141684 KB Output is correct
56 Correct 864 ms 188076 KB Output is correct
57 Correct 923 ms 188008 KB Output is correct
58 Correct 1748 ms 186088 KB Output is correct
59 Correct 1849 ms 185876 KB Output is correct
60 Correct 1821 ms 186552 KB Output is correct
61 Correct 1839 ms 186184 KB Output is correct
62 Correct 1611 ms 157172 KB Output is correct
63 Correct 1616 ms 157200 KB Output is correct
64 Correct 1784 ms 178904 KB Output is correct
65 Correct 1102 ms 151308 KB Output is correct
66 Correct 1391 ms 95824 KB Output is correct
67 Correct 1730 ms 96128 KB Output is correct
68 Correct 1481 ms 95924 KB Output is correct
69 Correct 1102 ms 95432 KB Output is correct
70 Correct 1661 ms 96112 KB Output is correct
71 Correct 1657 ms 96064 KB Output is correct
72 Correct 1681 ms 96056 KB Output is correct
73 Correct 1412 ms 95916 KB Output is correct
74 Correct 1506 ms 95836 KB Output is correct
75 Correct 1444 ms 95900 KB Output is correct
76 Correct 1123 ms 95616 KB Output is correct
77 Correct 1131 ms 95524 KB Output is correct
78 Correct 1205 ms 95528 KB Output is correct
79 Correct 1018 ms 95232 KB Output is correct
80 Correct 980 ms 95152 KB Output is correct
81 Correct 992 ms 95024 KB Output is correct
82 Correct 988 ms 93316 KB Output is correct
83 Correct 1047 ms 93328 KB Output is correct
84 Correct 950 ms 92820 KB Output is correct
85 Correct 2368 ms 188320 KB Output is correct
86 Correct 236 ms 23468 KB Output is correct
87 Correct 147 ms 23428 KB Output is correct
88 Correct 1481 ms 188804 KB Output is correct
89 Correct 2335 ms 188244 KB Output is correct
90 Correct 1564 ms 191108 KB Output is correct
91 Correct 1509 ms 98560 KB Output is correct
92 Correct 1506 ms 98612 KB Output is correct
93 Correct 2035 ms 98648 KB Output is correct
94 Correct 1956 ms 145256 KB Output is correct
95 Correct 1925 ms 145352 KB Output is correct
96 Correct 2290 ms 145540 KB Output is correct
97 Correct 1137 ms 190684 KB Output is correct
98 Correct 1268 ms 192148 KB Output is correct
99 Correct 2350 ms 190464 KB Output is correct
100 Correct 2298 ms 190132 KB Output is correct
101 Correct 2486 ms 190940 KB Output is correct
102 Correct 2499 ms 190584 KB Output is correct
103 Correct 2739 ms 161144 KB Output is correct
104 Correct 2589 ms 161008 KB Output is correct
105 Correct 1947 ms 162260 KB Output is correct
106 Correct 1508 ms 146348 KB Output is correct
107 Correct 1739 ms 160624 KB Output is correct
108 Correct 2544 ms 183024 KB Output is correct
109 Correct 1774 ms 154012 KB Output is correct