oj.uz

Submission #477096

# Submission time Handle Problem Language Result Execution time Memory
477096 2021-09-30T09:32:05 Z ymm Bridges (APIO19_bridges) C++17
100 / 100
 2602 ms 9540 KB 
///
///   Yare Yare Daze
///

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

//#ifndef EVAL
//void dbg(){cerr << "!\n";}
//template<class T, class... U> void dbg(T x, U... y){cerr << x << ' '; dbg(y...);}
//#else
template<class... T> inline void dbg(T... x){}
//#endif

const int N = 100010;
const int S = 600;
int n, m, q;

int ep1[N], ep2[N], cur_wt[N], new_wt[N];
int par[N], cmp_size[N];
int qt[N], qa[N], qb[N];

int root(int v){while(par[v] != -1) v = par[v]; return v;}
int root_cmp(int v){
	int rt = root(v);
	while(v != rt) {
		int u = par[v];
		par[v] = rt;
		v = u;
	}
	return v;
}

vector<pii> dsu_rev;
void unite(int v, int u)
{
	dbg("unite", v, u);
	v = root(v); u = root(u);
	if(v == u) return;
	if(cmp_size[v] < cmp_size[u]) swap(v, u);
	par[u] = v;
	cmp_size[v] += cmp_size[u];
	dsu_rev.emplace_back(v, u);
}
void unite_cmp(int v, int u)
{
	dbg("unitec", v, u);
	v = root_cmp(v); u = root_cmp(u);
	if(v == u) return;
	if(cmp_size[v] < cmp_size[u]) swap(v, u);
	par[u] = v;
	cmp_size[v] += cmp_size[u];
}

void dsu_reverse()
{
	for(auto it = dsu_rev.end(); it != dsu_rev.begin();)
	{
		--it;
		dbg("rev", it->first, it->second);
		cmp_size[it->first] -= cmp_size[it->second];
		par[it->second] = -1;
	}
	dsu_rev.clear();
}

void init()
{
	fill(par,par+N,-1);
	fill(cmp_size,cmp_size+N,1);
}

void Input()
{
	#ifndef EVAL
	freopen("in.txt", "r", stdin);
	#else
	ios::sync_with_stdio(false); cin.tie(0);
	#endif
	mt19937_64 rd;
	//n=50000;m=100000;
	cin >> n >> m;
	Loop(i,0,m)
		//ep1[i]=rd()%n,ep2[i]=rd()%n,cur_wt[i]=rd();
		cin >> ep1[i] >> ep2[i] >> cur_wt[i], ep1[i]--, ep2[i]--;
	//q=100000;
	cin >> q;
	Loop(i,0,q){
		cin >> qt[i] >> qa[i] >> qb[i];
		qa[i]--;
		//qt[i] = 2; qa[i] = rand()%n; qb[i] = rand();
	}
}

int ans[N];
void Output()
{
	Loop(i,0,q) if(qt[i] == 2) cout << ans[i] << '\n';
	#ifndef EVAL
	cout << double(clock())/CLOCKS_PER_SEC << '\n';
	#endif
}

bool in_ivl[N];
set<pii, greater<pii>> srt_edge;
vector<pii> srt_car;

int main()
{
	Input();
	Loop(i,0,m) srt_edge.emplace(cur_wt[i], i);
	for(int l = 0; l < q; l += S)
	{
		int r = min(q, l+S);
		init();
		Loop(i,l,r) {
			if(qt[i] == 1) in_ivl[qa[i]] = 1;
			else           srt_car.emplace_back(qb[i], i);
		}
		sort(srt_car.begin(), srt_car.end(), greater<pii>());
		auto edge_pnt = srt_edge.begin();
		memcpy(new_wt, cur_wt, m*4);
		for(auto [car_wt, car] : srt_car)
		{
			dbg("test", car, car_wt, edge_pnt->first);
			while(edge_pnt != srt_edge.end() && edge_pnt->first >= car_wt){
				if(!in_ivl[edge_pnt->second])
					unite_cmp(ep1[edge_pnt->second], ep2[edge_pnt->second]);
				edge_pnt++;
			}
			Loop(i,l,car) if(qt[i] == 1) new_wt[qa[i]] = qb[i]; 
			Loop(i,l,r) {
				if(qt[i] == 1) dbg("qt", qa[i], new_wt[qa[i]], car_wt);
				if(qt[i] == 1 && new_wt[qa[i]] >= car_wt) unite(ep1[qa[i]], ep2[qa[i]]);
			}
			ans[car] = cmp_size[root(qa[car])];
			dsu_reverse();
			Loop(i,l,car) if(qt[i] == 1) new_wt[qa[i]] = cur_wt[qa[i]];
		}
		srt_car.clear();
		Loop(i,l,r) if(qt[i] == 1) {
			int e = qa[i], w = qb[i];
			in_ivl[e] = 0;
			srt_edge.erase({cur_wt[e], e});
			cur_wt[e] = w;
			srt_edge.insert({cur_wt[e], e});
		}
	}
	Output();
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 32 ms 1348 KB Output is correct
4 Correct 16 ms 1304 KB Output is correct
5 Correct 41 ms 1276 KB Output is correct
6 Correct 32 ms 1284 KB Output is correct
7 Correct 36 ms 1288 KB Output is correct
8 Correct 41 ms 1280 KB Output is correct
9 Correct 37 ms 1280 KB Output is correct
10 Correct 41 ms 1280 KB Output is correct
11 Correct 41 ms 1280 KB Output is correct
12 Correct 45 ms 1228 KB Output is correct
13 Correct 45 ms 1228 KB Output is correct
14 Correct 44 ms 1284 KB Output is correct
15 Correct 47 ms 1276 KB Output is correct
16 Correct 37 ms 1228 KB Output is correct
17 Correct 40 ms 1280 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 5908 KB Output is correct
2 Correct 1390 ms 5912 KB Output is correct
3 Correct 1475 ms 6040 KB Output is correct
4 Correct 1375 ms 5864 KB Output is correct
5 Correct 1428 ms 5984 KB Output is correct
6 Correct 1872 ms 6108 KB Output is correct
7 Correct 1831 ms 6200 KB Output is correct
8 Correct 1698 ms 6096 KB Output is correct
9 Correct 113 ms 2852 KB Output is correct
10 Correct 1004 ms 6068 KB Output is correct
11 Correct 1010 ms 6068 KB Output is correct
12 Correct 1228 ms 6328 KB Output is correct
13 Correct 1116 ms 5828 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 4812 KB Output is correct
2 Correct 648 ms 3296 KB Output is correct
3 Correct 1051 ms 4952 KB Output is correct
4 Correct 1065 ms 4940 KB Output is correct
5 Correct 123 ms 2884 KB Output is correct
6 Correct 1052 ms 4892 KB Output is correct
7 Correct 914 ms 4884 KB Output is correct
8 Correct 816 ms 4804 KB Output is correct
9 Correct 678 ms 5040 KB Output is correct
10 Correct 655 ms 4912 KB Output is correct
11 Correct 635 ms 4764 KB Output is correct
12 Correct 628 ms 4768 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2232 ms 9376 KB Output is correct
2 Correct 118 ms 2884 KB Output is correct
3 Correct 190 ms 7448 KB Output is correct
4 Correct 98 ms 7440 KB Output is correct
5 Correct 1301 ms 9416 KB Output is correct
6 Correct 2230 ms 9356 KB Output is correct
7 Correct 1537 ms 9384 KB Output is correct
8 Correct 850 ms 5980 KB Output is correct
9 Correct 923 ms 6044 KB Output is correct
10 Correct 898 ms 6156 KB Output is correct
11 Correct 1767 ms 7600 KB Output is correct
12 Correct 1579 ms 7560 KB Output is correct
13 Correct 1697 ms 7764 KB Output is correct
14 Correct 1010 ms 9484 KB Output is correct
15 Correct 1242 ms 9540 KB Output is correct
16 Correct 2244 ms 9312 KB Output is correct
17 Correct 2045 ms 9304 KB Output is correct
18 Correct 2001 ms 9396 KB Output is correct
19 Correct 2154 ms 9228 KB Output is correct
20 Correct 1680 ms 8556 KB Output is correct
21 Correct 1578 ms 8416 KB Output is correct
22 Correct 1791 ms 9132 KB Output is correct
23 Correct 1258 ms 8372 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1508 ms 5908 KB Output is correct
2 Correct 1390 ms 5912 KB Output is correct
3 Correct 1475 ms 6040 KB Output is correct
4 Correct 1375 ms 5864 KB Output is correct
5 Correct 1428 ms 5984 KB Output is correct
6 Correct 1872 ms 6108 KB Output is correct
7 Correct 1831 ms 6200 KB Output is correct
8 Correct 1698 ms 6096 KB Output is correct
9 Correct 113 ms 2852 KB Output is correct
10 Correct 1004 ms 6068 KB Output is correct
11 Correct 1010 ms 6068 KB Output is correct
12 Correct 1228 ms 6328 KB Output is correct
13 Correct 1116 ms 5828 KB Output is correct
14 Correct 963 ms 4812 KB Output is correct
15 Correct 648 ms 3296 KB Output is correct
16 Correct 1051 ms 4952 KB Output is correct
17 Correct 1065 ms 4940 KB Output is correct
18 Correct 123 ms 2884 KB Output is correct
19 Correct 1052 ms 4892 KB Output is correct
20 Correct 914 ms 4884 KB Output is correct
21 Correct 816 ms 4804 KB Output is correct
22 Correct 678 ms 5040 KB Output is correct
23 Correct 655 ms 4912 KB Output is correct
24 Correct 635 ms 4764 KB Output is correct
25 Correct 628 ms 4768 KB Output is correct
26 Correct 1217 ms 5864 KB Output is correct
27 Correct 1499 ms 5992 KB Output is correct
28 Correct 1350 ms 5960 KB Output is correct
29 Correct 1085 ms 6044 KB Output is correct
30 Correct 1500 ms 5996 KB Output is correct
31 Correct 1508 ms 6000 KB Output is correct
32 Correct 1564 ms 5996 KB Output is correct
33 Correct 1489 ms 5904 KB Output is correct
34 Correct 1436 ms 5956 KB Output is correct
35 Correct 1372 ms 6036 KB Output is correct
36 Correct 1110 ms 6172 KB Output is correct
37 Correct 1134 ms 6056 KB Output is correct
38 Correct 1118 ms 5996 KB Output is correct
39 Correct 962 ms 5956 KB Output is correct
40 Correct 930 ms 6156 KB Output is correct
41 Correct 914 ms 6100 KB Output is correct
42 Correct 853 ms 5920 KB Output is correct
43 Correct 824 ms 6028 KB Output is correct
44 Correct 831 ms 5952 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 32 ms 1348 KB Output is correct
4 Correct 16 ms 1304 KB Output is correct
5 Correct 41 ms 1276 KB Output is correct
6 Correct 32 ms 1284 KB Output is correct
7 Correct 36 ms 1288 KB Output is correct
8 Correct 41 ms 1280 KB Output is correct
9 Correct 37 ms 1280 KB Output is correct
10 Correct 41 ms 1280 KB Output is correct
11 Correct 41 ms 1280 KB Output is correct
12 Correct 45 ms 1228 KB Output is correct
13 Correct 45 ms 1228 KB Output is correct
14 Correct 44 ms 1284 KB Output is correct
15 Correct 47 ms 1276 KB Output is correct
16 Correct 37 ms 1228 KB Output is correct
17 Correct 40 ms 1280 KB Output is correct
18 Correct 1508 ms 5908 KB Output is correct
19 Correct 1390 ms 5912 KB Output is correct
20 Correct 1475 ms 6040 KB Output is correct
21 Correct 1375 ms 5864 KB Output is correct
22 Correct 1428 ms 5984 KB Output is correct
23 Correct 1872 ms 6108 KB Output is correct
24 Correct 1831 ms 6200 KB Output is correct
25 Correct 1698 ms 6096 KB Output is correct
26 Correct 113 ms 2852 KB Output is correct
27 Correct 1004 ms 6068 KB Output is correct
28 Correct 1010 ms 6068 KB Output is correct
29 Correct 1228 ms 6328 KB Output is correct
30 Correct 1116 ms 5828 KB Output is correct
31 Correct 963 ms 4812 KB Output is correct
32 Correct 648 ms 3296 KB Output is correct
33 Correct 1051 ms 4952 KB Output is correct
34 Correct 1065 ms 4940 KB Output is correct
35 Correct 123 ms 2884 KB Output is correct
36 Correct 1052 ms 4892 KB Output is correct
37 Correct 914 ms 4884 KB Output is correct
38 Correct 816 ms 4804 KB Output is correct
39 Correct 678 ms 5040 KB Output is correct
40 Correct 655 ms 4912 KB Output is correct
41 Correct 635 ms 4764 KB Output is correct
42 Correct 628 ms 4768 KB Output is correct
43 Correct 2232 ms 9376 KB Output is correct
44 Correct 118 ms 2884 KB Output is correct
45 Correct 190 ms 7448 KB Output is correct
46 Correct 98 ms 7440 KB Output is correct
47 Correct 1301 ms 9416 KB Output is correct
48 Correct 2230 ms 9356 KB Output is correct
49 Correct 1537 ms 9384 KB Output is correct
50 Correct 850 ms 5980 KB Output is correct
51 Correct 923 ms 6044 KB Output is correct
52 Correct 898 ms 6156 KB Output is correct
53 Correct 1767 ms 7600 KB Output is correct
54 Correct 1579 ms 7560 KB Output is correct
55 Correct 1697 ms 7764 KB Output is correct
56 Correct 1010 ms 9484 KB Output is correct
57 Correct 1242 ms 9540 KB Output is correct
58 Correct 2244 ms 9312 KB Output is correct
59 Correct 2045 ms 9304 KB Output is correct
60 Correct 2001 ms 9396 KB Output is correct
61 Correct 2154 ms 9228 KB Output is correct
62 Correct 1680 ms 8556 KB Output is correct
63 Correct 1578 ms 8416 KB Output is correct
64 Correct 1791 ms 9132 KB Output is correct
65 Correct 1258 ms 8372 KB Output is correct
66 Correct 1217 ms 5864 KB Output is correct
67 Correct 1499 ms 5992 KB Output is correct
68 Correct 1350 ms 5960 KB Output is correct
69 Correct 1085 ms 6044 KB Output is correct
70 Correct 1500 ms 5996 KB Output is correct
71 Correct 1508 ms 6000 KB Output is correct
72 Correct 1564 ms 5996 KB Output is correct
73 Correct 1489 ms 5904 KB Output is correct
74 Correct 1436 ms 5956 KB Output is correct
75 Correct 1372 ms 6036 KB Output is correct
76 Correct 1110 ms 6172 KB Output is correct
77 Correct 1134 ms 6056 KB Output is correct
78 Correct 1118 ms 5996 KB Output is correct
79 Correct 962 ms 5956 KB Output is correct
80 Correct 930 ms 6156 KB Output is correct
81 Correct 914 ms 6100 KB Output is correct
82 Correct 853 ms 5920 KB Output is correct
83 Correct 824 ms 6028 KB Output is correct
84 Correct 831 ms 5952 KB Output is correct
85 Correct 2281 ms 9148 KB Output is correct
86 Correct 249 ms 7748 KB Output is correct
87 Correct 111 ms 7556 KB Output is correct
88 Correct 1580 ms 9284 KB Output is correct
89 Correct 2391 ms 9312 KB Output is correct
90 Correct 1546 ms 9404 KB Output is correct
91 Correct 1381 ms 5968 KB Output is correct
92 Correct 1390 ms 6024 KB Output is correct
93 Correct 1718 ms 6028 KB Output is correct
94 Correct 1895 ms 7492 KB Output is correct
95 Correct 1850 ms 7508 KB Output is correct
96 Correct 1726 ms 7640 KB Output is correct
97 Correct 1359 ms 9432 KB Output is correct
98 Correct 1370 ms 8996 KB Output is correct
99 Correct 2458 ms 9212 KB Output is correct
100 Correct 2503 ms 9132 KB Output is correct
101 Correct 2602 ms 9320 KB Output is correct
102 Correct 2554 ms 9140 KB Output is correct
103 Correct 1941 ms 8396 KB Output is correct
104 Correct 1909 ms 8192 KB Output is correct
105 Correct 1702 ms 8036 KB Output is correct
106 Correct 1410 ms 7420 KB Output is correct
107 Correct 1686 ms 8464 KB Output is correct
108 Correct 2155 ms 9008 KB Output is correct
109 Correct 1518 ms 8000 KB Output is correct