oj.uz

Submission #398369

# Submission time Handle Problem Language Result Execution time Memory
398369 2021-05-04T08:14:24 Z oolimry Bridges (APIO19_bridges) C++17
100 / 100
 1677 ms 13656 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<int, int> ii;
const int UPD = 1;
const int QRY = 2;

int edgeW[100005];
int U[100005];
int V[100005]; ///if B == -1, then is query
vector<ii> history[100005];
int n, m, Q;

int T[100005];
int queryW[100005];
int X[100005];
int ans[100005];


int p[50005];
int sz[50005];
int rak[50005];
inline void reset(){
	for(int i = 1;i <= n;i++) p[i] = i, sz[i] = 1, rak[i] = 0;
}

inline int findSet(int u){
	if(p[u] == u) return u;
	else return p[u] = findSet(p[u]);
}

inline void unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return;
	
	if(rak[u] > rak[v]) swap(u,v);
	
	if(rak[u] == rak[v]) rak[v]++;
	p[u] = v;
	sz[v] += sz[u];
}

bool changed[100005];
vector<int> order;
vector<int> neworder;
int ptr = 1;
inline void catchup(int limit){
	vector<int> C;
	for(;ptr <= limit;ptr++){
		if(T[ptr] == UPD){
			edgeW[X[ptr]] = queryW[ptr];
			C.push_back(X[ptr]);
			changed[X[ptr]] = true;
		}
	}
	
	sort(all(C), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	C.erase(unique(all(C)), C.end());
	
	auto it = order.begin();
	for(int e : C){
		int w = edgeW[e];
		while(it != order.end()){
			if(changed[*it]){
				it++;
				continue;
			}
			if(edgeW[*it] < w) break;
			else neworder.push_back(*it);
			it++;
		}
		neworder.push_back(e);
	}
	while(it != order.end()){
		if(not changed[*it]) neworder.push_back(*it);
		it++;
	}
	
	for(int e : C) changed[e] = false;
	swap(order,neworder); neworder.clear();	
}

vector<int> adj[50005];
bool vis[50005];

int dfs(int u){
	int res = sz[u];
	vis[u] = true;
	for(int v : adj[u]){
		if(not vis[v]){
			res += dfs(v);
		}
	}
	return res;
}


inline void solve(int L, int R){
	catchup(L);
	
	vector<int> stuff;
	vector<int> changededges;
	for(int i = L;i <= R;i++){
		stuff.push_back(i);
		if(T[i] == UPD) changededges.push_back(X[i]);
	}
	
	for(int x : changededges) changed[x] = true;
	
	reset();
	sort(all(stuff), [&](int a, int b){ return queryW[a] > queryW[b]; });
	
	auto it = order.begin();
	for(int qid : stuff){ ///decreasing w
		int w = queryW[qid];
		if(T[qid] == UPD) continue;
		
		while(it != order.end()){
			if(edgeW[*it] < w) break;
			else{
				int e = *it;
				if(not changed[e]){
					unionSet(U[e], V[e]);
				}
				it++;
			}
		}
		
		///if is query
		vector<int> special;
		for(int e : changededges){
			auto it = upper_bound(all(history[e]), ii(qid,-1)); it--;
			if(it->second < w) continue; ///edge weight not enough to handle car weight
			
			int u = findSet(U[e]), v = findSet(V[e]);
			if(u == v){
				special.push_back(u);
			}
			else{
				adj[u].push_back(v);
				adj[v].push_back(u);
				special.push_back(u);
				special.push_back(v);
			}
		}
		
		int source = findSet(X[qid]);
		special.push_back(source);
		
		int res = dfs(source);
		ans[qid] = res;
		
		///reset the stuff
		for(int u : special) vis[u] = false, adj[u].clear();
	}
	///reset the stuff
	for(int e : changededges) changed[e] = false;
}

const int B1 = 400; ///minimum size to proceed
const int B2 = 250; ///max number of updates to handle
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> m;
	for(int i = 1;i <= m;i++) cin >> U[i] >> V[i] >> edgeW[i];
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	cin >> Q;
	for(int i = 1;i <= Q;i++) cin >> T[i] >> X[i] >> queryW[i];
	
	order.resize(m);
	for(int i = 1;i <= m;i++) order[i-1] = i;
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	 
	for(int i = 1;i <= m;i++) history[i].push_back(ii(0, edgeW[i]));
	for(int i = 1;i <= Q;i++){
		if(T[i] == UPD) history[X[i]].push_back(ii(i, queryW[i]));
	}
	
	///bruh prunning
	int L = -1, R = -1, cnt = 0;
	for(int i = 1;i <= Q;i++){
		if(L == -1){
			if(T[i] == QRY) L = i, R = i;
		}
		else{
			if(T[i] == UPD) cnt++;
			else R = i;
		}
		
		if((R-L+1 >= B1 and cnt >= B2) or i == Q){
			solve(L,R);
			cnt = 0, L = -1, R = -1;
		}
	}
	
	for(int i = 1;i <= Q;i++){
		if(T[i] == QRY) cout << ans[i] << '\n';
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 50 ms 4164 KB Output is correct
4 Correct 9 ms 4172 KB Output is correct
5 Correct 82 ms 4120 KB Output is correct
6 Correct 71 ms 4100 KB Output is correct
7 Correct 78 ms 4100 KB Output is correct
8 Correct 71 ms 4104 KB Output is correct
9 Correct 88 ms 4104 KB Output is correct
10 Correct 82 ms 4092 KB Output is correct
11 Correct 71 ms 4096 KB Output is correct
12 Correct 78 ms 4112 KB Output is correct
13 Correct 73 ms 4048 KB Output is correct
14 Correct 69 ms 4116 KB Output is correct
15 Correct 81 ms 4100 KB Output is correct
16 Correct 76 ms 4116 KB Output is correct
17 Correct 75 ms 4112 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1243 ms 10812 KB Output is correct
2 Correct 1212 ms 10316 KB Output is correct
3 Correct 1243 ms 10352 KB Output is correct
4 Correct 1321 ms 10244 KB Output is correct
5 Correct 1309 ms 10324 KB Output is correct
6 Correct 1589 ms 9544 KB Output is correct
7 Correct 1491 ms 9532 KB Output is correct
8 Correct 1457 ms 9500 KB Output is correct
9 Correct 56 ms 5928 KB Output is correct
10 Correct 1217 ms 10240 KB Output is correct
11 Correct 1142 ms 10312 KB Output is correct
12 Correct 1677 ms 9292 KB Output is correct
13 Correct 903 ms 9936 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 10596 KB Output is correct
2 Correct 846 ms 6980 KB Output is correct
3 Correct 1094 ms 9036 KB Output is correct
4 Correct 970 ms 8976 KB Output is correct
5 Correct 50 ms 5952 KB Output is correct
6 Correct 1036 ms 8924 KB Output is correct
7 Correct 924 ms 8952 KB Output is correct
8 Correct 814 ms 8896 KB Output is correct
9 Correct 1140 ms 8344 KB Output is correct
10 Correct 912 ms 8232 KB Output is correct
11 Correct 680 ms 9436 KB Output is correct
12 Correct 658 ms 9416 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 11700 KB Output is correct
2 Correct 52 ms 6332 KB Output is correct
3 Correct 55 ms 9616 KB Output is correct
4 Correct 47 ms 9664 KB Output is correct
5 Correct 110 ms 12908 KB Output is correct
6 Correct 120 ms 12132 KB Output is correct
7 Correct 86 ms 13172 KB Output is correct
8 Correct 90 ms 10684 KB Output is correct
9 Correct 88 ms 9388 KB Output is correct
10 Correct 89 ms 10556 KB Output is correct
11 Correct 129 ms 11008 KB Output is correct
12 Correct 130 ms 12328 KB Output is correct
13 Correct 105 ms 12468 KB Output is correct
14 Correct 79 ms 13240 KB Output is correct
15 Correct 81 ms 13152 KB Output is correct
16 Correct 126 ms 13452 KB Output is correct
17 Correct 134 ms 13656 KB Output is correct
18 Correct 112 ms 13116 KB Output is correct
19 Correct 143 ms 13572 KB Output is correct
20 Correct 106 ms 12928 KB Output is correct
21 Correct 103 ms 12772 KB Output is correct
22 Correct 123 ms 13620 KB Output is correct
23 Correct 75 ms 12088 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1243 ms 10812 KB Output is correct
2 Correct 1212 ms 10316 KB Output is correct
3 Correct 1243 ms 10352 KB Output is correct
4 Correct 1321 ms 10244 KB Output is correct
5 Correct 1309 ms 10324 KB Output is correct
6 Correct 1589 ms 9544 KB Output is correct
7 Correct 1491 ms 9532 KB Output is correct
8 Correct 1457 ms 9500 KB Output is correct
9 Correct 56 ms 5928 KB Output is correct
10 Correct 1217 ms 10240 KB Output is correct
11 Correct 1142 ms 10312 KB Output is correct
12 Correct 1677 ms 9292 KB Output is correct
13 Correct 903 ms 9936 KB Output is correct
14 Correct 1004 ms 10596 KB Output is correct
15 Correct 846 ms 6980 KB Output is correct
16 Correct 1094 ms 9036 KB Output is correct
17 Correct 970 ms 8976 KB Output is correct
18 Correct 50 ms 5952 KB Output is correct
19 Correct 1036 ms 8924 KB Output is correct
20 Correct 924 ms 8952 KB Output is correct
21 Correct 814 ms 8896 KB Output is correct
22 Correct 1140 ms 8344 KB Output is correct
23 Correct 912 ms 8232 KB Output is correct
24 Correct 680 ms 9436 KB Output is correct
25 Correct 658 ms 9416 KB Output is correct
26 Correct 1321 ms 10460 KB Output is correct
27 Correct 1456 ms 10272 KB Output is correct
28 Correct 1302 ms 10284 KB Output is correct
29 Correct 973 ms 10308 KB Output is correct
30 Correct 1454 ms 10464 KB Output is correct
31 Correct 1442 ms 10540 KB Output is correct
32 Correct 1510 ms 10384 KB Output is correct
33 Correct 1284 ms 10432 KB Output is correct
34 Correct 1299 ms 10348 KB Output is correct
35 Correct 1331 ms 10484 KB Output is correct
36 Correct 1049 ms 10516 KB Output is correct
37 Correct 1052 ms 10344 KB Output is correct
38 Correct 1045 ms 10560 KB Output is correct
39 Correct 724 ms 9520 KB Output is correct
40 Correct 741 ms 9592 KB Output is correct
41 Correct 714 ms 9504 KB Output is correct
42 Correct 846 ms 10932 KB Output is correct
43 Correct 876 ms 10928 KB Output is correct
44 Correct 829 ms 10744 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 50 ms 4164 KB Output is correct
4 Correct 9 ms 4172 KB Output is correct
5 Correct 82 ms 4120 KB Output is correct
6 Correct 71 ms 4100 KB Output is correct
7 Correct 78 ms 4100 KB Output is correct
8 Correct 71 ms 4104 KB Output is correct
9 Correct 88 ms 4104 KB Output is correct
10 Correct 82 ms 4092 KB Output is correct
11 Correct 71 ms 4096 KB Output is correct
12 Correct 78 ms 4112 KB Output is correct
13 Correct 73 ms 4048 KB Output is correct
14 Correct 69 ms 4116 KB Output is correct
15 Correct 81 ms 4100 KB Output is correct
16 Correct 76 ms 4116 KB Output is correct
17 Correct 75 ms 4112 KB Output is correct
18 Correct 1243 ms 10812 KB Output is correct
19 Correct 1212 ms 10316 KB Output is correct
20 Correct 1243 ms 10352 KB Output is correct
21 Correct 1321 ms 10244 KB Output is correct
22 Correct 1309 ms 10324 KB Output is correct
23 Correct 1589 ms 9544 KB Output is correct
24 Correct 1491 ms 9532 KB Output is correct
25 Correct 1457 ms 9500 KB Output is correct
26 Correct 56 ms 5928 KB Output is correct
27 Correct 1217 ms 10240 KB Output is correct
28 Correct 1142 ms 10312 KB Output is correct
29 Correct 1677 ms 9292 KB Output is correct
30 Correct 903 ms 9936 KB Output is correct
31 Correct 1004 ms 10596 KB Output is correct
32 Correct 846 ms 6980 KB Output is correct
33 Correct 1094 ms 9036 KB Output is correct
34 Correct 970 ms 8976 KB Output is correct
35 Correct 50 ms 5952 KB Output is correct
36 Correct 1036 ms 8924 KB Output is correct
37 Correct 924 ms 8952 KB Output is correct
38 Correct 814 ms 8896 KB Output is correct
39 Correct 1140 ms 8344 KB Output is correct
40 Correct 912 ms 8232 KB Output is correct
41 Correct 680 ms 9436 KB Output is correct
42 Correct 658 ms 9416 KB Output is correct
43 Correct 111 ms 11700 KB Output is correct
44 Correct 52 ms 6332 KB Output is correct
45 Correct 55 ms 9616 KB Output is correct
46 Correct 47 ms 9664 KB Output is correct
47 Correct 110 ms 12908 KB Output is correct
48 Correct 120 ms 12132 KB Output is correct
49 Correct 86 ms 13172 KB Output is correct
50 Correct 90 ms 10684 KB Output is correct
51 Correct 88 ms 9388 KB Output is correct
52 Correct 89 ms 10556 KB Output is correct
53 Correct 129 ms 11008 KB Output is correct
54 Correct 130 ms 12328 KB Output is correct
55 Correct 105 ms 12468 KB Output is correct
56 Correct 79 ms 13240 KB Output is correct
57 Correct 81 ms 13152 KB Output is correct
58 Correct 126 ms 13452 KB Output is correct
59 Correct 134 ms 13656 KB Output is correct
60 Correct 112 ms 13116 KB Output is correct
61 Correct 143 ms 13572 KB Output is correct
62 Correct 106 ms 12928 KB Output is correct
63 Correct 103 ms 12772 KB Output is correct
64 Correct 123 ms 13620 KB Output is correct
65 Correct 75 ms 12088 KB Output is correct
66 Correct 1321 ms 10460 KB Output is correct
67 Correct 1456 ms 10272 KB Output is correct
68 Correct 1302 ms 10284 KB Output is correct
69 Correct 973 ms 10308 KB Output is correct
70 Correct 1454 ms 10464 KB Output is correct
71 Correct 1442 ms 10540 KB Output is correct
72 Correct 1510 ms 10384 KB Output is correct
73 Correct 1284 ms 10432 KB Output is correct
74 Correct 1299 ms 10348 KB Output is correct
75 Correct 1331 ms 10484 KB Output is correct
76 Correct 1049 ms 10516 KB Output is correct
77 Correct 1052 ms 10344 KB Output is correct
78 Correct 1045 ms 10560 KB Output is correct
79 Correct 724 ms 9520 KB Output is correct
80 Correct 741 ms 9592 KB Output is correct
81 Correct 714 ms 9504 KB Output is correct
82 Correct 846 ms 10932 KB Output is correct
83 Correct 876 ms 10928 KB Output is correct
84 Correct 829 ms 10744 KB Output is correct
85 Correct 1468 ms 12692 KB Output is correct
86 Correct 129 ms 9408 KB Output is correct
87 Correct 101 ms 9868 KB Output is correct
88 Correct 1165 ms 12624 KB Output is correct
89 Correct 1491 ms 12736 KB Output is correct
90 Correct 1176 ms 12488 KB Output is correct
91 Correct 1316 ms 10472 KB Output is correct
92 Correct 1295 ms 10440 KB Output is correct
93 Correct 1489 ms 9720 KB Output is correct
94 Correct 1454 ms 11544 KB Output is correct
95 Correct 1495 ms 11664 KB Output is correct
96 Correct 1355 ms 10860 KB Output is correct
97 Correct 829 ms 11972 KB Output is correct
98 Correct 1106 ms 12664 KB Output is correct
99 Correct 1588 ms 12604 KB Output is correct
100 Correct 1558 ms 12620 KB Output is correct
101 Correct 1603 ms 12756 KB Output is correct
102 Correct 1621 ms 12660 KB Output is correct
103 Correct 1466 ms 11180 KB Output is correct
104 Correct 1446 ms 11268 KB Output is correct
105 Correct 1347 ms 11504 KB Output is correct
106 Correct 1184 ms 11132 KB Output is correct
107 Correct 973 ms 10908 KB Output is correct
108 Correct 1461 ms 11836 KB Output is correct
109 Correct 1278 ms 11012 KB Output is correct