oj.uz

답안 #559725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559725 2022-05-10T13:13:06 Z heavylightdecomp 다리 (APIO19_bridges) C++14
100 / 100
 2817 ms 170108 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
const int mxN = 1e5+5, bsz = 1024;
struct dsu {
	int n;
	int par[mxN], ccsz[mxN], h[bsz*mxN], hsz;
	void prep(int _n) {n = _n; for(int i = 1; i <= n; i++) par[i] = i, ccsz[i] = 1; }
	int find(int x) { while(par[x]!=x) x = par[x]; return x; }
	inline void push(int u, int v) {++hsz; h[hsz] = u;}
	void merge(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(ccsz[a] > ccsz[b]) swap(a,b);
		push(a,b);
		par[a] = b;
		ccsz[b] += ccsz[a];
	}
	void rollback(int to) {
		while(hsz > to) { ccsz[par[h[hsz]]] -= ccsz[h[hsz]]; par[h[hsz]] = h[hsz]; --hsz;}
	}
} D;

int ans[mxN], u[mxN], v[mxN], d[mxN], t[mxN], p[mxN], w[mxN], c[mxN];
vector<int> good[mxN];
signed main() {
	//freopen("bridge.in", "r", stdin);
	//freopen("bridge.out", "w", stdout);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> d[i];
	int q; cin >> q;
	for(int i = 1; i <= q; i++) cin >> t[i] >> p[i] >> w[i];
	for(int l = 1; l <= q; l += bsz) {
		int r = min(l+bsz-1,q);
		iota(D.par+1, D.par+mxN, 1);
		memset(c, 0, sizeof c);
		for(int i = 0; i < mxN; i++) D.ccsz[i] = 1;
		vector<int> ask, upd, same, bad;
		for(int i = l; i <= r; i++) if(t[i]==1) c[p[i]]=1; else ask.push_back(i);
		for(int i = 1; i <= m; i++) { if(!c[i]) same.push_back(i); else bad.push_back(i); }
		for(int i = l; i <= r; i++) {
			if(t[i]==1) d[p[i]] = w[i]; else for(int cand : bad) if(d[cand] >= w[i]) good[i].push_back(cand);
		}
		sort(begin(same), end(same), [&](int a, int b) { return d[a] > d[b]; });
		sort(begin(ask), end(ask), [&](int a, int b) { return w[a] > w[b]; });
		int fbe = 0;
		const int ssz = same.size();
		for(int query : ask) {
			while(fbe < ssz && d[same[fbe]] >= w[query]) D.merge(u[same[fbe]], v[same[fbe]]), fbe++;
			int before = D.hsz;
			for(int also : good[query]) D.merge(u[also], v[also]);
			ans[query] = D.ccsz[D.find(p[query])];
			D.rollback(before); 
		}
	}
	for(int i = 1; i <= q; i++) if(t[i]==2) cout << ans[i] << '\n';
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 38 ms 9880 KB Output is correct
4 Correct 10 ms 4068 KB Output is correct
5 Correct 19 ms 5776 KB Output is correct
6 Correct 17 ms 5740 KB Output is correct
7 Correct 17 ms 5612 KB Output is correct
8 Correct 20 ms 5480 KB Output is correct
9 Correct 20 ms 6676 KB Output is correct
10 Correct 21 ms 5668 KB Output is correct
11 Correct 26 ms 5608 KB Output is correct
12 Correct 23 ms 6004 KB Output is correct
13 Correct 25 ms 6524 KB Output is correct
14 Correct 24 ms 6080 KB Output is correct
15 Correct 21 ms 5660 KB Output is correct
16 Correct 18 ms 5976 KB Output is correct
17 Correct 19 ms 5984 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1456 ms 93912 KB Output is correct
2 Correct 1462 ms 93748 KB Output is correct
3 Correct 1495 ms 93876 KB Output is correct
4 Correct 1477 ms 93460 KB Output is correct
5 Correct 1481 ms 93836 KB Output is correct
6 Correct 2164 ms 170108 KB Output is correct
7 Correct 2154 ms 165936 KB Output is correct
8 Correct 2151 ms 166272 KB Output is correct
9 Correct 91 ms 5816 KB Output is correct
10 Correct 1395 ms 135164 KB Output is correct
11 Correct 1276 ms 125392 KB Output is correct
12 Correct 1494 ms 74780 KB Output is correct
13 Correct 1357 ms 68052 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1290 ms 87224 KB Output is correct
2 Correct 988 ms 101196 KB Output is correct
3 Correct 1566 ms 123148 KB Output is correct
4 Correct 1294 ms 88400 KB Output is correct
5 Correct 111 ms 6816 KB Output is correct
6 Correct 1476 ms 108540 KB Output is correct
7 Correct 1208 ms 80804 KB Output is correct
8 Correct 1065 ms 64364 KB Output is correct
9 Correct 908 ms 56020 KB Output is correct
10 Correct 776 ms 44712 KB Output is correct
11 Correct 841 ms 53092 KB Output is correct
12 Correct 745 ms 42816 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1753 ms 26656 KB Output is correct
2 Correct 97 ms 6916 KB Output is correct
3 Correct 233 ms 8048 KB Output is correct
4 Correct 165 ms 8144 KB Output is correct
5 Correct 1014 ms 28660 KB Output is correct
6 Correct 1883 ms 30092 KB Output is correct
7 Correct 1050 ms 28532 KB Output is correct
8 Correct 988 ms 28216 KB Output is correct
9 Correct 959 ms 28428 KB Output is correct
10 Correct 935 ms 28232 KB Output is correct
11 Correct 1324 ms 29592 KB Output is correct
12 Correct 1363 ms 29600 KB Output is correct
13 Correct 1333 ms 29468 KB Output is correct
14 Correct 918 ms 28596 KB Output is correct
15 Correct 936 ms 28628 KB Output is correct
16 Correct 1742 ms 30248 KB Output is correct
17 Correct 1732 ms 30544 KB Output is correct
18 Correct 1759 ms 30784 KB Output is correct
19 Correct 1756 ms 30448 KB Output is correct
20 Correct 1470 ms 29492 KB Output is correct
21 Correct 1472 ms 29712 KB Output is correct
22 Correct 1672 ms 29884 KB Output is correct
23 Correct 1012 ms 26568 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1456 ms 93912 KB Output is correct
2 Correct 1462 ms 93748 KB Output is correct
3 Correct 1495 ms 93876 KB Output is correct
4 Correct 1477 ms 93460 KB Output is correct
5 Correct 1481 ms 93836 KB Output is correct
6 Correct 2164 ms 170108 KB Output is correct
7 Correct 2154 ms 165936 KB Output is correct
8 Correct 2151 ms 166272 KB Output is correct
9 Correct 91 ms 5816 KB Output is correct
10 Correct 1395 ms 135164 KB Output is correct
11 Correct 1276 ms 125392 KB Output is correct
12 Correct 1494 ms 74780 KB Output is correct
13 Correct 1357 ms 68052 KB Output is correct
14 Correct 1290 ms 87224 KB Output is correct
15 Correct 988 ms 101196 KB Output is correct
16 Correct 1566 ms 123148 KB Output is correct
17 Correct 1294 ms 88400 KB Output is correct
18 Correct 111 ms 6816 KB Output is correct
19 Correct 1476 ms 108540 KB Output is correct
20 Correct 1208 ms 80804 KB Output is correct
21 Correct 1065 ms 64364 KB Output is correct
22 Correct 908 ms 56020 KB Output is correct
23 Correct 776 ms 44712 KB Output is correct
24 Correct 841 ms 53092 KB Output is correct
25 Correct 745 ms 42816 KB Output is correct
26 Correct 1597 ms 96180 KB Output is correct
27 Correct 1878 ms 133948 KB Output is correct
28 Correct 1602 ms 94312 KB Output is correct
29 Correct 1259 ms 50692 KB Output is correct
30 Correct 1938 ms 115888 KB Output is correct
31 Correct 2060 ms 119016 KB Output is correct
32 Correct 2066 ms 120016 KB Output is correct
33 Correct 1735 ms 94524 KB Output is correct
34 Correct 1736 ms 94692 KB Output is correct
35 Correct 1749 ms 95052 KB Output is correct
36 Correct 1342 ms 57596 KB Output is correct
37 Correct 1369 ms 56472 KB Output is correct
38 Correct 1306 ms 54928 KB Output is correct
39 Correct 1152 ms 40584 KB Output is correct
40 Correct 1144 ms 39900 KB Output is correct
41 Correct 1076 ms 39412 KB Output is correct
42 Correct 978 ms 38380 KB Output is correct
43 Correct 995 ms 37780 KB Output is correct
44 Correct 984 ms 37044 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 38 ms 9880 KB Output is correct
4 Correct 10 ms 4068 KB Output is correct
5 Correct 19 ms 5776 KB Output is correct
6 Correct 17 ms 5740 KB Output is correct
7 Correct 17 ms 5612 KB Output is correct
8 Correct 20 ms 5480 KB Output is correct
9 Correct 20 ms 6676 KB Output is correct
10 Correct 21 ms 5668 KB Output is correct
11 Correct 26 ms 5608 KB Output is correct
12 Correct 23 ms 6004 KB Output is correct
13 Correct 25 ms 6524 KB Output is correct
14 Correct 24 ms 6080 KB Output is correct
15 Correct 21 ms 5660 KB Output is correct
16 Correct 18 ms 5976 KB Output is correct
17 Correct 19 ms 5984 KB Output is correct
18 Correct 1456 ms 93912 KB Output is correct
19 Correct 1462 ms 93748 KB Output is correct
20 Correct 1495 ms 93876 KB Output is correct
21 Correct 1477 ms 93460 KB Output is correct
22 Correct 1481 ms 93836 KB Output is correct
23 Correct 2164 ms 170108 KB Output is correct
24 Correct 2154 ms 165936 KB Output is correct
25 Correct 2151 ms 166272 KB Output is correct
26 Correct 91 ms 5816 KB Output is correct
27 Correct 1395 ms 135164 KB Output is correct
28 Correct 1276 ms 125392 KB Output is correct
29 Correct 1494 ms 74780 KB Output is correct
30 Correct 1357 ms 68052 KB Output is correct
31 Correct 1290 ms 87224 KB Output is correct
32 Correct 988 ms 101196 KB Output is correct
33 Correct 1566 ms 123148 KB Output is correct
34 Correct 1294 ms 88400 KB Output is correct
35 Correct 111 ms 6816 KB Output is correct
36 Correct 1476 ms 108540 KB Output is correct
37 Correct 1208 ms 80804 KB Output is correct
38 Correct 1065 ms 64364 KB Output is correct
39 Correct 908 ms 56020 KB Output is correct
40 Correct 776 ms 44712 KB Output is correct
41 Correct 841 ms 53092 KB Output is correct
42 Correct 745 ms 42816 KB Output is correct
43 Correct 1753 ms 26656 KB Output is correct
44 Correct 97 ms 6916 KB Output is correct
45 Correct 233 ms 8048 KB Output is correct
46 Correct 165 ms 8144 KB Output is correct
47 Correct 1014 ms 28660 KB Output is correct
48 Correct 1883 ms 30092 KB Output is correct
49 Correct 1050 ms 28532 KB Output is correct
50 Correct 988 ms 28216 KB Output is correct
51 Correct 959 ms 28428 KB Output is correct
52 Correct 935 ms 28232 KB Output is correct
53 Correct 1324 ms 29592 KB Output is correct
54 Correct 1363 ms 29600 KB Output is correct
55 Correct 1333 ms 29468 KB Output is correct
56 Correct 918 ms 28596 KB Output is correct
57 Correct 936 ms 28628 KB Output is correct
58 Correct 1742 ms 30248 KB Output is correct
59 Correct 1732 ms 30544 KB Output is correct
60 Correct 1759 ms 30784 KB Output is correct
61 Correct 1756 ms 30448 KB Output is correct
62 Correct 1470 ms 29492 KB Output is correct
63 Correct 1472 ms 29712 KB Output is correct
64 Correct 1672 ms 29884 KB Output is correct
65 Correct 1012 ms 26568 KB Output is correct
66 Correct 1597 ms 96180 KB Output is correct
67 Correct 1878 ms 133948 KB Output is correct
68 Correct 1602 ms 94312 KB Output is correct
69 Correct 1259 ms 50692 KB Output is correct
70 Correct 1938 ms 115888 KB Output is correct
71 Correct 2060 ms 119016 KB Output is correct
72 Correct 2066 ms 120016 KB Output is correct
73 Correct 1735 ms 94524 KB Output is correct
74 Correct 1736 ms 94692 KB Output is correct
75 Correct 1749 ms 95052 KB Output is correct
76 Correct 1342 ms 57596 KB Output is correct
77 Correct 1369 ms 56472 KB Output is correct
78 Correct 1306 ms 54928 KB Output is correct
79 Correct 1152 ms 40584 KB Output is correct
80 Correct 1144 ms 39900 KB Output is correct
81 Correct 1076 ms 39412 KB Output is correct
82 Correct 978 ms 38380 KB Output is correct
83 Correct 995 ms 37780 KB Output is correct
84 Correct 984 ms 37044 KB Output is correct
85 Correct 2174 ms 98628 KB Output is correct
86 Correct 261 ms 14244 KB Output is correct
87 Correct 195 ms 19516 KB Output is correct
88 Correct 1454 ms 117960 KB Output is correct
89 Correct 2197 ms 96908 KB Output is correct
90 Correct 1461 ms 124556 KB Output is correct
91 Correct 1610 ms 95992 KB Output is correct
92 Correct 1599 ms 95920 KB Output is correct
93 Correct 2256 ms 141288 KB Output is correct
94 Correct 2009 ms 97468 KB Output is correct
95 Correct 2264 ms 97388 KB Output is correct
96 Correct 2517 ms 145984 KB Output is correct
97 Correct 1372 ms 62260 KB Output is correct
98 Correct 1420 ms 58748 KB Output is correct
99 Correct 2534 ms 99600 KB Output is correct
100 Correct 2435 ms 98312 KB Output is correct
101 Correct 2621 ms 98556 KB Output is correct
102 Correct 2766 ms 98388 KB Output is correct
103 Correct 2783 ms 156200 KB Output is correct
104 Correct 2817 ms 155064 KB Output is correct
105 Correct 2226 ms 69656 KB Output is correct
106 Correct 1815 ms 49696 KB Output is correct
107 Correct 2043 ms 76248 KB Output is correct
108 Correct 2605 ms 133216 KB Output is correct
109 Correct 1968 ms 140496 KB Output is correct