oj.uz

Submission #677081

# Submission time Handle Problem Language Result Execution time Memory
677081 2023-01-02T08:44:30 Z Dan4Life Bridges (APIO19_bridges) C++17
100 / 100
 2282 ms 56992 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define int long long
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()

const int B = 1200;
const int maxn = (int)1e5+10;

int n, m, q;
stack<int> st; bool ch[maxn]; 
int u[maxn], v[maxn], w[maxn];
int t[maxn], s[maxn], w2[maxn];
int p[maxn], sz[maxn], ans[maxn];
vector<int> edge[B], updE, fixE;

void rs(){ iota(p,p+n+1,0); fill(sz,sz+n+1,1); }
int findSet(int i) { return p[i]==i?i:findSet(p[i]); }

void unionSet(int a, int b){
	a=findSet(a), b=findSet(b);
	if(a==b) return;
	if(sz[a] < sz[b]) swap(a,b);
	sz[a]+=sz[b]; st.push(b); p[b]=a; 
}

void rollback(int Size){
	while(SZ(st)>Size){
		int x = st.top(); st.pop();
		sz[p[x]]-=sz[x], p[x]=x;
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	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] >> s[i] >> w2[i];

	for(int l = 1; l <= q; l+=B){
		int r = min(q+1, l+B), j=0;
		fill(ch,ch+m+1,false); rs();
		updE.clear(); fixE.clear();
		for(int i = 0; i < B; i++) edge[i].clear();

		for(int i = l; i < r; i++)
			if(t[i]==1 and !ch[s[i]]) 
				updE.pb(i), ch[s[i]]=1;
		for(int i = 1; i <= m; i++) if(!ch[i]) fixE.pb(i);

		for(int i = l; i < r; i++){
			if(t[i]==1) w[s[i]]=w2[i];
			else for(auto j : updE) 
				if(w[s[j]]>=w2[i]) edge[i-l].pb(s[j]);
		}
		
		vector<int> ord(r-l,0); iota(all(ord),l);
		sort(all(fixE), [&](int i, int j){ return w[i]>w[j]; });
		sort(all(ord), [&](int i, int j){ return w2[i]>w2[j]; });
		
		for(auto i : ord){
			if(t[i]==1) continue;
			while(j<SZ(fixE) and w[fixE[j]]>=w2[i])
				unionSet(u[fixE[j]],v[fixE[j]]), j++;
			int pr = SZ(st);
			for(auto j : edge[i-l]) unionSet(u[j],v[j]); 
			ans[i] = sz[findSet(s[i])]; rollback(pr);
		}
	}
	for(int i = 1; i <= q; i++) if(t[i]==2) cout << ans[i] << "\n";
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 40 ms 5544 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 12 ms 2028 KB Output is correct
6 Correct 9 ms 1748 KB Output is correct
7 Correct 13 ms 2004 KB Output is correct
8 Correct 15 ms 1936 KB Output is correct
9 Correct 12 ms 1916 KB Output is correct
10 Correct 14 ms 2032 KB Output is correct
11 Correct 13 ms 1908 KB Output is correct
12 Correct 13 ms 2008 KB Output is correct
13 Correct 16 ms 2704 KB Output is correct
14 Correct 16 ms 2512 KB Output is correct
15 Correct 13 ms 2028 KB Output is correct
16 Correct 12 ms 2024 KB Output is correct
17 Correct 13 ms 2004 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1371 ms 50052 KB Output is correct
2 Correct 1449 ms 50116 KB Output is correct
3 Correct 1422 ms 50200 KB Output is correct
4 Correct 1487 ms 50044 KB Output is correct
5 Correct 1493 ms 50128 KB Output is correct
6 Correct 2260 ms 50076 KB Output is correct
7 Correct 2218 ms 50028 KB Output is correct
8 Correct 2282 ms 50080 KB Output is correct
9 Correct 34 ms 3760 KB Output is correct
10 Correct 1322 ms 49940 KB Output is correct
11 Correct 1285 ms 50052 KB Output is correct
12 Correct 1193 ms 43404 KB Output is correct
13 Correct 1296 ms 54852 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 37372 KB Output is correct
2 Correct 959 ms 19160 KB Output is correct
3 Correct 1465 ms 37472 KB Output is correct
4 Correct 1205 ms 37468 KB Output is correct
5 Correct 40 ms 3704 KB Output is correct
6 Correct 1328 ms 37428 KB Output is correct
7 Correct 1058 ms 37436 KB Output is correct
8 Correct 923 ms 37096 KB Output is correct
9 Correct 719 ms 30300 KB Output is correct
10 Correct 632 ms 29772 KB Output is correct
11 Correct 768 ms 38444 KB Output is correct
12 Correct 642 ms 37520 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1386 ms 41940 KB Output is correct
2 Correct 34 ms 3792 KB Output is correct
3 Correct 151 ms 4304 KB Output is correct
4 Correct 70 ms 4332 KB Output is correct
5 Correct 739 ms 42032 KB Output is correct
6 Correct 1430 ms 41944 KB Output is correct
7 Correct 795 ms 41908 KB Output is correct
8 Correct 667 ms 40712 KB Output is correct
9 Correct 668 ms 40692 KB Output is correct
10 Correct 680 ms 40908 KB Output is correct
11 Correct 1151 ms 41656 KB Output is correct
12 Correct 1104 ms 41620 KB Output is correct
13 Correct 1000 ms 41828 KB Output is correct
14 Correct 669 ms 41988 KB Output is correct
15 Correct 723 ms 41964 KB Output is correct
16 Correct 1387 ms 42364 KB Output is correct
17 Correct 1484 ms 42372 KB Output is correct
18 Correct 1331 ms 42324 KB Output is correct
19 Correct 1380 ms 42212 KB Output is correct
20 Correct 1110 ms 41852 KB Output is correct
21 Correct 1121 ms 41896 KB Output is correct
22 Correct 1307 ms 41428 KB Output is correct
23 Correct 790 ms 38200 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1371 ms 50052 KB Output is correct
2 Correct 1449 ms 50116 KB Output is correct
3 Correct 1422 ms 50200 KB Output is correct
4 Correct 1487 ms 50044 KB Output is correct
5 Correct 1493 ms 50128 KB Output is correct
6 Correct 2260 ms 50076 KB Output is correct
7 Correct 2218 ms 50028 KB Output is correct
8 Correct 2282 ms 50080 KB Output is correct
9 Correct 34 ms 3760 KB Output is correct
10 Correct 1322 ms 49940 KB Output is correct
11 Correct 1285 ms 50052 KB Output is correct
12 Correct 1193 ms 43404 KB Output is correct
13 Correct 1296 ms 54852 KB Output is correct
14 Correct 1164 ms 37372 KB Output is correct
15 Correct 959 ms 19160 KB Output is correct
16 Correct 1465 ms 37472 KB Output is correct
17 Correct 1205 ms 37468 KB Output is correct
18 Correct 40 ms 3704 KB Output is correct
19 Correct 1328 ms 37428 KB Output is correct
20 Correct 1058 ms 37436 KB Output is correct
21 Correct 923 ms 37096 KB Output is correct
22 Correct 719 ms 30300 KB Output is correct
23 Correct 632 ms 29772 KB Output is correct
24 Correct 768 ms 38444 KB Output is correct
25 Correct 642 ms 37520 KB Output is correct
26 Correct 1448 ms 49880 KB Output is correct
27 Correct 1844 ms 49924 KB Output is correct
28 Correct 1495 ms 49920 KB Output is correct
29 Correct 959 ms 48880 KB Output is correct
30 Correct 1810 ms 49872 KB Output is correct
31 Correct 1827 ms 49836 KB Output is correct
32 Correct 1802 ms 50152 KB Output is correct
33 Correct 1557 ms 50112 KB Output is correct
34 Correct 1538 ms 50016 KB Output is correct
35 Correct 1527 ms 50096 KB Output is correct
36 Correct 1107 ms 49400 KB Output is correct
37 Correct 1060 ms 49316 KB Output is correct
38 Correct 1108 ms 49156 KB Output is correct
39 Correct 886 ms 42140 KB Output is correct
40 Correct 862 ms 42096 KB Output is correct
41 Correct 747 ms 42128 KB Output is correct
42 Correct 820 ms 47940 KB Output is correct
43 Correct 802 ms 47904 KB Output is correct
44 Correct 754 ms 47692 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 40 ms 5544 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 12 ms 2028 KB Output is correct
6 Correct 9 ms 1748 KB Output is correct
7 Correct 13 ms 2004 KB Output is correct
8 Correct 15 ms 1936 KB Output is correct
9 Correct 12 ms 1916 KB Output is correct
10 Correct 14 ms 2032 KB Output is correct
11 Correct 13 ms 1908 KB Output is correct
12 Correct 13 ms 2008 KB Output is correct
13 Correct 16 ms 2704 KB Output is correct
14 Correct 16 ms 2512 KB Output is correct
15 Correct 13 ms 2028 KB Output is correct
16 Correct 12 ms 2024 KB Output is correct
17 Correct 13 ms 2004 KB Output is correct
18 Correct 1371 ms 50052 KB Output is correct
19 Correct 1449 ms 50116 KB Output is correct
20 Correct 1422 ms 50200 KB Output is correct
21 Correct 1487 ms 50044 KB Output is correct
22 Correct 1493 ms 50128 KB Output is correct
23 Correct 2260 ms 50076 KB Output is correct
24 Correct 2218 ms 50028 KB Output is correct
25 Correct 2282 ms 50080 KB Output is correct
26 Correct 34 ms 3760 KB Output is correct
27 Correct 1322 ms 49940 KB Output is correct
28 Correct 1285 ms 50052 KB Output is correct
29 Correct 1193 ms 43404 KB Output is correct
30 Correct 1296 ms 54852 KB Output is correct
31 Correct 1164 ms 37372 KB Output is correct
32 Correct 959 ms 19160 KB Output is correct
33 Correct 1465 ms 37472 KB Output is correct
34 Correct 1205 ms 37468 KB Output is correct
35 Correct 40 ms 3704 KB Output is correct
36 Correct 1328 ms 37428 KB Output is correct
37 Correct 1058 ms 37436 KB Output is correct
38 Correct 923 ms 37096 KB Output is correct
39 Correct 719 ms 30300 KB Output is correct
40 Correct 632 ms 29772 KB Output is correct
41 Correct 768 ms 38444 KB Output is correct
42 Correct 642 ms 37520 KB Output is correct
43 Correct 1386 ms 41940 KB Output is correct
44 Correct 34 ms 3792 KB Output is correct
45 Correct 151 ms 4304 KB Output is correct
46 Correct 70 ms 4332 KB Output is correct
47 Correct 739 ms 42032 KB Output is correct
48 Correct 1430 ms 41944 KB Output is correct
49 Correct 795 ms 41908 KB Output is correct
50 Correct 667 ms 40712 KB Output is correct
51 Correct 668 ms 40692 KB Output is correct
52 Correct 680 ms 40908 KB Output is correct
53 Correct 1151 ms 41656 KB Output is correct
54 Correct 1104 ms 41620 KB Output is correct
55 Correct 1000 ms 41828 KB Output is correct
56 Correct 669 ms 41988 KB Output is correct
57 Correct 723 ms 41964 KB Output is correct
58 Correct 1387 ms 42364 KB Output is correct
59 Correct 1484 ms 42372 KB Output is correct
60 Correct 1331 ms 42324 KB Output is correct
61 Correct 1380 ms 42212 KB Output is correct
62 Correct 1110 ms 41852 KB Output is correct
63 Correct 1121 ms 41896 KB Output is correct
64 Correct 1307 ms 41428 KB Output is correct
65 Correct 790 ms 38200 KB Output is correct
66 Correct 1448 ms 49880 KB Output is correct
67 Correct 1844 ms 49924 KB Output is correct
68 Correct 1495 ms 49920 KB Output is correct
69 Correct 959 ms 48880 KB Output is correct
70 Correct 1810 ms 49872 KB Output is correct
71 Correct 1827 ms 49836 KB Output is correct
72 Correct 1802 ms 50152 KB Output is correct
73 Correct 1557 ms 50112 KB Output is correct
74 Correct 1538 ms 50016 KB Output is correct
75 Correct 1527 ms 50096 KB Output is correct
76 Correct 1107 ms 49400 KB Output is correct
77 Correct 1060 ms 49316 KB Output is correct
78 Correct 1108 ms 49156 KB Output is correct
79 Correct 886 ms 42140 KB Output is correct
80 Correct 862 ms 42096 KB Output is correct
81 Correct 747 ms 42128 KB Output is correct
82 Correct 820 ms 47940 KB Output is correct
83 Correct 802 ms 47904 KB Output is correct
84 Correct 754 ms 47692 KB Output is correct
85 Correct 1768 ms 51544 KB Output is correct
86 Correct 185 ms 11416 KB Output is correct
87 Correct 111 ms 13624 KB Output is correct
88 Correct 1145 ms 51460 KB Output is correct
89 Correct 1788 ms 51484 KB Output is correct
90 Correct 1178 ms 51396 KB Output is correct
91 Correct 1437 ms 49908 KB Output is correct
92 Correct 1442 ms 50020 KB Output is correct
93 Correct 2246 ms 49768 KB Output is correct
94 Correct 1573 ms 51164 KB Output is correct
95 Correct 1648 ms 51212 KB Output is correct
96 Correct 1939 ms 51096 KB Output is correct
97 Correct 867 ms 44356 KB Output is correct
98 Correct 917 ms 55832 KB Output is correct
99 Correct 1822 ms 51868 KB Output is correct
100 Correct 1776 ms 51828 KB Output is correct
101 Correct 1905 ms 52068 KB Output is correct
102 Correct 1900 ms 52004 KB Output is correct
103 Correct 2069 ms 51388 KB Output is correct
104 Correct 2054 ms 51364 KB Output is correct
105 Correct 1617 ms 56484 KB Output is correct
106 Correct 1163 ms 56992 KB Output is correct
107 Correct 1334 ms 44396 KB Output is correct
108 Correct 1874 ms 50908 KB Output is correct
109 Correct 1448 ms 47504 KB Output is correct