oj.uz

답안 #792881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792881 2023-07-25T10:16:58 Z phoenix0423 다리 (APIO19_bridges) C++17
100 / 100
 1687 ms 228112 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
const int maxn = 1e5 + 5;
ll u[maxn], v[maxn], w[maxn];
ll t[maxn], x[maxn], y[maxn], ch[maxn]; // [bridge, new weight] or [start, car weight]
ll ans[maxn];
vector<int> to_join[maxn];
int n, m, q;
const int b = 1200;

struct dsu_save{
	int u, rku, v, rkv;
	dsu_save(){}
	dsu_save(int _u, int _rku, int _v, int _rkv) : u(_u), rku(_rku), v(_v), rkv(_rkv){}
};
struct DSU{
	vector<int> par, siz;
	int n;
	stack<int> stk;
	DSU(){}
	DSU(int _n) : n(_n){}
	void init(){
		siz = vector<int>(n, 1);
		par.resize(n);
		for(int i = 0; i < n; i++) par[i] = i;
	}
	int root(int x){
		return x == par[x] ? x : root(par[x]);
	}
	void unite(int x, int y){
		x = root(x);
		y = root(y);
		if(x == y) return;
		if(siz[x] > siz[y]) swap(x, y);
		stk.push(x);
		par[x] = y;
		siz[y] += siz[x];
	}
	void roll_back(int sz){
		while(stk.size() > sz){
			auto u = stk.top(); stk.pop();
			siz[par[u]] -= siz[u];
			par[u] = u;
		}
	}
};
int main(void){

	fastio;
	cin>>n>>m;
	DSU dsu(n + 1);
	for(int i = 1; i <= m; i++){
		cin >> u[i] >> v[i] >> w[i];
	}
	cin>>q;
	for(int i = 1; i <= q; i++){
		cin >> t[i] >> x[i] >> y[i];
	}
	for(int l = 1; l <= q; l += b){
		int r = min(q + 1, l + b);
		fill(ch, ch + maxn, false);
		dsu.init();
		vector<int> ask, upd, unchanged;

		for(int i = l; i < r; i++){
			if(t[i] == 1){
				ch[x[i]] = true;
				upd.pb(i);
			}
			else ask.pb(i);
		}
		for(int i = 1; i <= m; i++){
			if(!ch[i]) unchanged.pb(i);
		}
		for(int i = l; i < r; i++){
			if(t[i] == 1) w[x[i]] = y[i];
			else{
				to_join[i].clear();
				for(auto j : upd){
					if(w[x[j]] >= y[i]) to_join[i].pb(x[j]);
				}
			}
		}
		sort(ask.begin(), ask.end(), [](int a, int b){ return y[a] > y[b];});
		sort(unchanged.begin(), unchanged.end(), [](int a, int b){ return w[a] > w[b];});
		// processing queries
		int unptr = 0;
		for(auto i : ask){
			while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
				dsu.unite(u[unchanged[unptr]], v[unchanged[unptr]]);
				unptr++;
			}
			int prev_sz = dsu.stk.size();
			for(auto j : to_join[i]){
				dsu.unite(u[j], v[j]);
			}
			ans[i] = dsu.siz[dsu.root(x[i])];
			dsu.roll_back(prev_sz);
		}
	}
	for(int i = 1; i <= q; i++) if(t[i] == 2) cout << ans[i] << "\n";
}

Compilation message

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   while(stk.size() > sz){
      |         ~~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    while(unptr < unchanged.size() && w[unchanged[unptr]] >= y[i]){ // no need to roll back
      |          ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 1 ms 3412 KB Output is correct
3 Correct 38 ms 12148 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 34 ms 14152 KB Output is correct
6 Correct 25 ms 14504 KB Output is correct
7 Correct 28 ms 15308 KB Output is correct
8 Correct 35 ms 11492 KB Output is correct
9 Correct 38 ms 23100 KB Output is correct
10 Correct 37 ms 12780 KB Output is correct
11 Correct 37 ms 12096 KB Output is correct
12 Correct 46 ms 15200 KB Output is correct
13 Correct 41 ms 13268 KB Output is correct
14 Correct 37 ms 11708 KB Output is correct
15 Correct 42 ms 12808 KB Output is correct
16 Correct 31 ms 18200 KB Output is correct
17 Correct 32 ms 15980 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 986 ms 112944 KB Output is correct
2 Correct 1006 ms 112176 KB Output is correct
3 Correct 1022 ms 112596 KB Output is correct
4 Correct 1022 ms 112000 KB Output is correct
5 Correct 1004 ms 112728 KB Output is correct
6 Correct 1221 ms 225836 KB Output is correct
7 Correct 1197 ms 226636 KB Output is correct
8 Correct 1234 ms 226388 KB Output is correct
9 Correct 30 ms 6732 KB Output is correct
10 Correct 663 ms 175972 KB Output is correct
11 Correct 636 ms 145620 KB Output is correct
12 Correct 834 ms 83632 KB Output is correct
13 Correct 807 ms 105132 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 772 ms 106448 KB Output is correct
2 Correct 509 ms 154852 KB Output is correct
3 Correct 821 ms 164372 KB Output is correct
4 Correct 746 ms 105528 KB Output is correct
5 Correct 31 ms 6740 KB Output is correct
6 Correct 839 ms 132992 KB Output is correct
7 Correct 713 ms 95836 KB Output is correct
8 Correct 628 ms 73684 KB Output is correct
9 Correct 515 ms 58372 KB Output is correct
10 Correct 486 ms 45736 KB Output is correct
11 Correct 561 ms 56792 KB Output is correct
12 Correct 541 ms 45188 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1288 ms 27472 KB Output is correct
2 Correct 30 ms 6740 KB Output is correct
3 Correct 157 ms 7112 KB Output is correct
4 Correct 73 ms 7012 KB Output is correct
5 Correct 659 ms 27740 KB Output is correct
6 Correct 1257 ms 27412 KB Output is correct
7 Correct 655 ms 27432 KB Output is correct
8 Correct 590 ms 25940 KB Output is correct
9 Correct 569 ms 25868 KB Output is correct
10 Correct 569 ms 26028 KB Output is correct
11 Correct 928 ms 26896 KB Output is correct
12 Correct 915 ms 26940 KB Output is correct
13 Correct 962 ms 27112 KB Output is correct
14 Correct 605 ms 27612 KB Output is correct
15 Correct 640 ms 27480 KB Output is correct
16 Correct 1309 ms 27600 KB Output is correct
17 Correct 1283 ms 27616 KB Output is correct
18 Correct 1269 ms 27744 KB Output is correct
19 Correct 1289 ms 27832 KB Output is correct
20 Correct 1062 ms 27352 KB Output is correct
21 Correct 1066 ms 27436 KB Output is correct
22 Correct 1210 ms 27308 KB Output is correct
23 Correct 688 ms 25524 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 986 ms 112944 KB Output is correct
2 Correct 1006 ms 112176 KB Output is correct
3 Correct 1022 ms 112596 KB Output is correct
4 Correct 1022 ms 112000 KB Output is correct
5 Correct 1004 ms 112728 KB Output is correct
6 Correct 1221 ms 225836 KB Output is correct
7 Correct 1197 ms 226636 KB Output is correct
8 Correct 1234 ms 226388 KB Output is correct
9 Correct 30 ms 6732 KB Output is correct
10 Correct 663 ms 175972 KB Output is correct
11 Correct 636 ms 145620 KB Output is correct
12 Correct 834 ms 83632 KB Output is correct
13 Correct 807 ms 105132 KB Output is correct
14 Correct 772 ms 106448 KB Output is correct
15 Correct 509 ms 154852 KB Output is correct
16 Correct 821 ms 164372 KB Output is correct
17 Correct 746 ms 105528 KB Output is correct
18 Correct 31 ms 6740 KB Output is correct
19 Correct 839 ms 132992 KB Output is correct
20 Correct 713 ms 95836 KB Output is correct
21 Correct 628 ms 73684 KB Output is correct
22 Correct 515 ms 58372 KB Output is correct
23 Correct 486 ms 45736 KB Output is correct
24 Correct 561 ms 56792 KB Output is correct
25 Correct 541 ms 45188 KB Output is correct
26 Correct 1022 ms 112232 KB Output is correct
27 Correct 1060 ms 171496 KB Output is correct
28 Correct 975 ms 110460 KB Output is correct
29 Correct 758 ms 54056 KB Output is correct
30 Correct 1094 ms 143168 KB Output is correct
31 Correct 1118 ms 148568 KB Output is correct
32 Correct 1152 ms 150120 KB Output is correct
33 Correct 1038 ms 108984 KB Output is correct
34 Correct 995 ms 109860 KB Output is correct
35 Correct 995 ms 109860 KB Output is correct
36 Correct 791 ms 62656 KB Output is correct
37 Correct 796 ms 60672 KB Output is correct
38 Correct 775 ms 58804 KB Output is correct
39 Correct 663 ms 39848 KB Output is correct
40 Correct 654 ms 38932 KB Output is correct
41 Correct 664 ms 38428 KB Output is correct
42 Correct 635 ms 37656 KB Output is correct
43 Correct 635 ms 36908 KB Output is correct
44 Correct 656 ms 36332 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 1 ms 3412 KB Output is correct
3 Correct 38 ms 12148 KB Output is correct
4 Correct 4 ms 3796 KB Output is correct
5 Correct 34 ms 14152 KB Output is correct
6 Correct 25 ms 14504 KB Output is correct
7 Correct 28 ms 15308 KB Output is correct
8 Correct 35 ms 11492 KB Output is correct
9 Correct 38 ms 23100 KB Output is correct
10 Correct 37 ms 12780 KB Output is correct
11 Correct 37 ms 12096 KB Output is correct
12 Correct 46 ms 15200 KB Output is correct
13 Correct 41 ms 13268 KB Output is correct
14 Correct 37 ms 11708 KB Output is correct
15 Correct 42 ms 12808 KB Output is correct
16 Correct 31 ms 18200 KB Output is correct
17 Correct 32 ms 15980 KB Output is correct
18 Correct 986 ms 112944 KB Output is correct
19 Correct 1006 ms 112176 KB Output is correct
20 Correct 1022 ms 112596 KB Output is correct
21 Correct 1022 ms 112000 KB Output is correct
22 Correct 1004 ms 112728 KB Output is correct
23 Correct 1221 ms 225836 KB Output is correct
24 Correct 1197 ms 226636 KB Output is correct
25 Correct 1234 ms 226388 KB Output is correct
26 Correct 30 ms 6732 KB Output is correct
27 Correct 663 ms 175972 KB Output is correct
28 Correct 636 ms 145620 KB Output is correct
29 Correct 834 ms 83632 KB Output is correct
30 Correct 807 ms 105132 KB Output is correct
31 Correct 772 ms 106448 KB Output is correct
32 Correct 509 ms 154852 KB Output is correct
33 Correct 821 ms 164372 KB Output is correct
34 Correct 746 ms 105528 KB Output is correct
35 Correct 31 ms 6740 KB Output is correct
36 Correct 839 ms 132992 KB Output is correct
37 Correct 713 ms 95836 KB Output is correct
38 Correct 628 ms 73684 KB Output is correct
39 Correct 515 ms 58372 KB Output is correct
40 Correct 486 ms 45736 KB Output is correct
41 Correct 561 ms 56792 KB Output is correct
42 Correct 541 ms 45188 KB Output is correct
43 Correct 1288 ms 27472 KB Output is correct
44 Correct 30 ms 6740 KB Output is correct
45 Correct 157 ms 7112 KB Output is correct
46 Correct 73 ms 7012 KB Output is correct
47 Correct 659 ms 27740 KB Output is correct
48 Correct 1257 ms 27412 KB Output is correct
49 Correct 655 ms 27432 KB Output is correct
50 Correct 590 ms 25940 KB Output is correct
51 Correct 569 ms 25868 KB Output is correct
52 Correct 569 ms 26028 KB Output is correct
53 Correct 928 ms 26896 KB Output is correct
54 Correct 915 ms 26940 KB Output is correct
55 Correct 962 ms 27112 KB Output is correct
56 Correct 605 ms 27612 KB Output is correct
57 Correct 640 ms 27480 KB Output is correct
58 Correct 1309 ms 27600 KB Output is correct
59 Correct 1283 ms 27616 KB Output is correct
60 Correct 1269 ms 27744 KB Output is correct
61 Correct 1289 ms 27832 KB Output is correct
62 Correct 1062 ms 27352 KB Output is correct
63 Correct 1066 ms 27436 KB Output is correct
64 Correct 1210 ms 27308 KB Output is correct
65 Correct 688 ms 25524 KB Output is correct
66 Correct 1022 ms 112232 KB Output is correct
67 Correct 1060 ms 171496 KB Output is correct
68 Correct 975 ms 110460 KB Output is correct
69 Correct 758 ms 54056 KB Output is correct
70 Correct 1094 ms 143168 KB Output is correct
71 Correct 1118 ms 148568 KB Output is correct
72 Correct 1152 ms 150120 KB Output is correct
73 Correct 1038 ms 108984 KB Output is correct
74 Correct 995 ms 109860 KB Output is correct
75 Correct 995 ms 109860 KB Output is correct
76 Correct 791 ms 62656 KB Output is correct
77 Correct 796 ms 60672 KB Output is correct
78 Correct 775 ms 58804 KB Output is correct
79 Correct 663 ms 39848 KB Output is correct
80 Correct 654 ms 38932 KB Output is correct
81 Correct 664 ms 38428 KB Output is correct
82 Correct 635 ms 37656 KB Output is correct
83 Correct 635 ms 36908 KB Output is correct
84 Correct 656 ms 36332 KB Output is correct
85 Correct 1617 ms 114436 KB Output is correct
86 Correct 202 ms 15948 KB Output is correct
87 Correct 120 ms 26784 KB Output is correct
88 Correct 936 ms 140936 KB Output is correct
89 Correct 1617 ms 113024 KB Output is correct
90 Correct 932 ms 142360 KB Output is correct
91 Correct 1010 ms 112812 KB Output is correct
92 Correct 1016 ms 112552 KB Output is correct
93 Correct 1232 ms 227240 KB Output is correct
94 Correct 1364 ms 114144 KB Output is correct
95 Correct 1362 ms 114356 KB Output is correct
96 Correct 1535 ms 227164 KB Output is correct
97 Correct 777 ms 65916 KB Output is correct
98 Correct 768 ms 72736 KB Output is correct
99 Correct 1687 ms 116892 KB Output is correct
100 Correct 1643 ms 115368 KB Output is correct
101 Correct 1646 ms 114964 KB Output is correct
102 Correct 1654 ms 114516 KB Output is correct
103 Correct 1616 ms 227912 KB Output is correct
104 Correct 1577 ms 228112 KB Output is correct
105 Correct 1252 ms 107528 KB Output is correct
106 Correct 1088 ms 67808 KB Output is correct
107 Correct 1243 ms 82556 KB Output is correct
108 Correct 1631 ms 170080 KB Output is correct
109 Correct 1079 ms 224224 KB Output is correct