oj.uz

Submission #419530

# Submission time Handle Problem Language Result Execution time Memory
419530 2021-06-07T08:37:06 Z codebuster_10 Bridges (APIO19_bridges) C++17
100 / 100
 2684 ms 60840 KB 
#include <bits/stdc++.h>

using namespace std ;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}




















// solution by :- https://usaco.guide/problems/apio-2019bridges/solution







int n, m, q;


const int BLOCK_SIZE = 1000;
const int MAX_N = 5e4 + 1, MAX_M = 1e5 + 1;

stack<int> st;
int SZ[MAX_N], parent[MAX_N];


void reset(){
	iota(parent + 1, parent + n + 1, 1);
	fill(SZ + 1, SZ + n + 1, 1);
	return;
}

int find(int a){
	while(parent[a] != a) a = parent[a];
	return a;
}

void join(int a,int b){
	a = find(a), b = find(b);
	if(a == b) return;
	if(SZ[a] > SZ[b]) swap(a,b);
	// a is child of b now.
	st.push(a);
	SZ[b] += SZ[a], parent[a] = b;
	return; 
}

void roll_back(int req_size){
	while(int(st.size()) > req_size){
		int x = st.top(); st.pop();
		SZ[parent[x]] -= SZ[x];
		parent[x] = x;
	}
	return;
}

int u[MAX_M], v[MAX_M], w[MAX_M];
int t[MAX_M], x[MAX_M], y[MAX_M];
bool changed[MAX_M];
vector<int> to_join[BLOCK_SIZE];
int ans[MAX_M];

signed main(){
  setIO();
	rd(n,m);
	f(i,1,m+1){
		rd(u[i],v[i],w[i]);
	}
	rd(q);
	f(i,1,q+1) rd(t[i],x[i],y[i]);
	
	for(int l = 1; l <= q; l += BLOCK_SIZE){
		int r = min(q + 1, l + BLOCK_SIZE);
		reset();
		fill(changed + 1, changed + m + 1, false);
		
		
		vt<int> upd, ask, unchanged;
		f(i,l,r){
			if(t[i] == 1){
				changed[x[i]] = true;
				upd.pb(i);
			}else{
				ask.pb(i);
			}
		}
		
		f(i,1,m+1) if(!changed[i]) unchanged.pb(i);
		
		
		f(i,l,r){
			if(t[i] == 1){
				w[x[i]] = y[i];
			}else{
				to_join[i-l].clear();
				for(auto j : upd) if (w[x[j]] >= y[i]) to_join[i-l].push_back(x[j]);
			}
		}
		
		sort(all(ask),[&](auto A,auto B){
			return y[A] > y[B];
		});
		
		sort(all(unchanged),[&](auto A, auto B){
			return w[A] > w[B];
		});
		
		int ptr = 0;
		for(auto i : ask){
			while(ptr < sz(unchanged) && w[unchanged[ptr]] >= y[i]) {
				join(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = sz(st);
			for(auto j : to_join[i - l]) join(u[j], v[j]);
			ans[i] = SZ[find(x[i])];
			roll_back(prev_size);
		}
		
	}
	
	f(i,1,q+1) if(t[i] == 2) cout << ans[i] << endl;
	
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 39 ms 5124 KB Output is correct
4 Correct 5 ms 808 KB Output is correct
5 Correct 40 ms 5440 KB Output is correct
6 Correct 31 ms 5004 KB Output is correct
7 Correct 37 ms 6636 KB Output is correct
8 Correct 41 ms 4940 KB Output is correct
9 Correct 48 ms 8220 KB Output is correct
10 Correct 42 ms 5284 KB Output is correct
11 Correct 43 ms 4980 KB Output is correct
12 Correct 50 ms 5536 KB Output is correct
13 Correct 48 ms 5188 KB Output is correct
14 Correct 44 ms 4984 KB Output is correct
15 Correct 47 ms 5048 KB Output is correct
16 Correct 46 ms 7592 KB Output is correct
17 Correct 43 ms 6468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1639 ms 54276 KB Output is correct
2 Correct 1610 ms 54196 KB Output is correct
3 Correct 1594 ms 54416 KB Output is correct
4 Correct 1673 ms 54340 KB Output is correct
5 Correct 1656 ms 54652 KB Output is correct
6 Correct 2406 ms 57836 KB Output is correct
7 Correct 2410 ms 57532 KB Output is correct
8 Correct 2396 ms 57604 KB Output is correct
9 Correct 46 ms 5040 KB Output is correct
10 Correct 1348 ms 56596 KB Output is correct
11 Correct 1217 ms 56504 KB Output is correct
12 Correct 1362 ms 50960 KB Output is correct
13 Correct 1447 ms 57264 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 38996 KB Output is correct
2 Correct 991 ms 20160 KB Output is correct
3 Correct 1526 ms 42068 KB Output is correct
4 Correct 1243 ms 39156 KB Output is correct
5 Correct 49 ms 4932 KB Output is correct
6 Correct 1476 ms 39104 KB Output is correct
7 Correct 1185 ms 38656 KB Output is correct
8 Correct 1012 ms 38528 KB Output is correct
9 Correct 836 ms 35632 KB Output is correct
10 Correct 737 ms 35600 KB Output is correct
11 Correct 888 ms 41480 KB Output is correct
12 Correct 790 ms 41292 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1939 ms 52624 KB Output is correct
2 Correct 45 ms 4948 KB Output is correct
3 Correct 195 ms 6772 KB Output is correct
4 Correct 97 ms 6908 KB Output is correct
5 Correct 1014 ms 51104 KB Output is correct
6 Correct 1783 ms 52536 KB Output is correct
7 Correct 967 ms 51200 KB Output is correct
8 Correct 868 ms 49920 KB Output is correct
9 Correct 868 ms 49972 KB Output is correct
10 Correct 893 ms 49940 KB Output is correct
11 Correct 1351 ms 51796 KB Output is correct
12 Correct 1360 ms 51904 KB Output is correct
13 Correct 1399 ms 51884 KB Output is correct
14 Correct 890 ms 51112 KB Output is correct
15 Correct 944 ms 51164 KB Output is correct
16 Correct 1857 ms 53044 KB Output is correct
17 Correct 1856 ms 53188 KB Output is correct
18 Correct 1827 ms 53536 KB Output is correct
19 Correct 1812 ms 53464 KB Output is correct
20 Correct 1521 ms 52356 KB Output is correct
21 Correct 1524 ms 52272 KB Output is correct
22 Correct 1796 ms 51996 KB Output is correct
23 Correct 1077 ms 46752 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1639 ms 54276 KB Output is correct
2 Correct 1610 ms 54196 KB Output is correct
3 Correct 1594 ms 54416 KB Output is correct
4 Correct 1673 ms 54340 KB Output is correct
5 Correct 1656 ms 54652 KB Output is correct
6 Correct 2406 ms 57836 KB Output is correct
7 Correct 2410 ms 57532 KB Output is correct
8 Correct 2396 ms 57604 KB Output is correct
9 Correct 46 ms 5040 KB Output is correct
10 Correct 1348 ms 56596 KB Output is correct
11 Correct 1217 ms 56504 KB Output is correct
12 Correct 1362 ms 50960 KB Output is correct
13 Correct 1447 ms 57264 KB Output is correct
14 Correct 1316 ms 38996 KB Output is correct
15 Correct 991 ms 20160 KB Output is correct
16 Correct 1526 ms 42068 KB Output is correct
17 Correct 1243 ms 39156 KB Output is correct
18 Correct 49 ms 4932 KB Output is correct
19 Correct 1476 ms 39104 KB Output is correct
20 Correct 1185 ms 38656 KB Output is correct
21 Correct 1012 ms 38528 KB Output is correct
22 Correct 836 ms 35632 KB Output is correct
23 Correct 737 ms 35600 KB Output is correct
24 Correct 888 ms 41480 KB Output is correct
25 Correct 790 ms 41292 KB Output is correct
26 Correct 1710 ms 54564 KB Output is correct
27 Correct 1990 ms 57660 KB Output is correct
28 Correct 1673 ms 54452 KB Output is correct
29 Correct 1208 ms 53756 KB Output is correct
30 Correct 1996 ms 57460 KB Output is correct
31 Correct 1974 ms 57620 KB Output is correct
32 Correct 2033 ms 57648 KB Output is correct
33 Correct 1635 ms 54364 KB Output is correct
34 Correct 1668 ms 54168 KB Output is correct
35 Correct 1675 ms 54280 KB Output is correct
36 Correct 1265 ms 53576 KB Output is correct
37 Correct 1237 ms 53812 KB Output is correct
38 Correct 1234 ms 53564 KB Output is correct
39 Correct 1048 ms 50768 KB Output is correct
40 Correct 1008 ms 50884 KB Output is correct
41 Correct 1006 ms 50752 KB Output is correct
42 Correct 1072 ms 54984 KB Output is correct
43 Correct 1000 ms 54920 KB Output is correct
44 Correct 1000 ms 54628 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 39 ms 5124 KB Output is correct
4 Correct 5 ms 808 KB Output is correct
5 Correct 40 ms 5440 KB Output is correct
6 Correct 31 ms 5004 KB Output is correct
7 Correct 37 ms 6636 KB Output is correct
8 Correct 41 ms 4940 KB Output is correct
9 Correct 48 ms 8220 KB Output is correct
10 Correct 42 ms 5284 KB Output is correct
11 Correct 43 ms 4980 KB Output is correct
12 Correct 50 ms 5536 KB Output is correct
13 Correct 48 ms 5188 KB Output is correct
14 Correct 44 ms 4984 KB Output is correct
15 Correct 47 ms 5048 KB Output is correct
16 Correct 46 ms 7592 KB Output is correct
17 Correct 43 ms 6468 KB Output is correct
18 Correct 1639 ms 54276 KB Output is correct
19 Correct 1610 ms 54196 KB Output is correct
20 Correct 1594 ms 54416 KB Output is correct
21 Correct 1673 ms 54340 KB Output is correct
22 Correct 1656 ms 54652 KB Output is correct
23 Correct 2406 ms 57836 KB Output is correct
24 Correct 2410 ms 57532 KB Output is correct
25 Correct 2396 ms 57604 KB Output is correct
26 Correct 46 ms 5040 KB Output is correct
27 Correct 1348 ms 56596 KB Output is correct
28 Correct 1217 ms 56504 KB Output is correct
29 Correct 1362 ms 50960 KB Output is correct
30 Correct 1447 ms 57264 KB Output is correct
31 Correct 1316 ms 38996 KB Output is correct
32 Correct 991 ms 20160 KB Output is correct
33 Correct 1526 ms 42068 KB Output is correct
34 Correct 1243 ms 39156 KB Output is correct
35 Correct 49 ms 4932 KB Output is correct
36 Correct 1476 ms 39104 KB Output is correct
37 Correct 1185 ms 38656 KB Output is correct
38 Correct 1012 ms 38528 KB Output is correct
39 Correct 836 ms 35632 KB Output is correct
40 Correct 737 ms 35600 KB Output is correct
41 Correct 888 ms 41480 KB Output is correct
42 Correct 790 ms 41292 KB Output is correct
43 Correct 1939 ms 52624 KB Output is correct
44 Correct 45 ms 4948 KB Output is correct
45 Correct 195 ms 6772 KB Output is correct
46 Correct 97 ms 6908 KB Output is correct
47 Correct 1014 ms 51104 KB Output is correct
48 Correct 1783 ms 52536 KB Output is correct
49 Correct 967 ms 51200 KB Output is correct
50 Correct 868 ms 49920 KB Output is correct
51 Correct 868 ms 49972 KB Output is correct
52 Correct 893 ms 49940 KB Output is correct
53 Correct 1351 ms 51796 KB Output is correct
54 Correct 1360 ms 51904 KB Output is correct
55 Correct 1399 ms 51884 KB Output is correct
56 Correct 890 ms 51112 KB Output is correct
57 Correct 944 ms 51164 KB Output is correct
58 Correct 1857 ms 53044 KB Output is correct
59 Correct 1856 ms 53188 KB Output is correct
60 Correct 1827 ms 53536 KB Output is correct
61 Correct 1812 ms 53464 KB Output is correct
62 Correct 1521 ms 52356 KB Output is correct
63 Correct 1524 ms 52272 KB Output is correct
64 Correct 1796 ms 51996 KB Output is correct
65 Correct 1077 ms 46752 KB Output is correct
66 Correct 1710 ms 54564 KB Output is correct
67 Correct 1990 ms 57660 KB Output is correct
68 Correct 1673 ms 54452 KB Output is correct
69 Correct 1208 ms 53756 KB Output is correct
70 Correct 1996 ms 57460 KB Output is correct
71 Correct 1974 ms 57620 KB Output is correct
72 Correct 2033 ms 57648 KB Output is correct
73 Correct 1635 ms 54364 KB Output is correct
74 Correct 1668 ms 54168 KB Output is correct
75 Correct 1675 ms 54280 KB Output is correct
76 Correct 1265 ms 53576 KB Output is correct
77 Correct 1237 ms 53812 KB Output is correct
78 Correct 1234 ms 53564 KB Output is correct
79 Correct 1048 ms 50768 KB Output is correct
80 Correct 1008 ms 50884 KB Output is correct
81 Correct 1006 ms 50752 KB Output is correct
82 Correct 1072 ms 54984 KB Output is correct
83 Correct 1000 ms 54920 KB Output is correct
84 Correct 1000 ms 54628 KB Output is correct
85 Correct 2457 ms 57220 KB Output is correct
86 Correct 226 ms 10792 KB Output is correct
87 Correct 143 ms 13500 KB Output is correct
88 Correct 1601 ms 58904 KB Output is correct
89 Correct 2417 ms 57284 KB Output is correct
90 Correct 1566 ms 58952 KB Output is correct
91 Correct 1814 ms 54380 KB Output is correct
92 Correct 1757 ms 54316 KB Output is correct
93 Correct 2487 ms 57040 KB Output is correct
94 Correct 2005 ms 57036 KB Output is correct
95 Correct 2024 ms 56900 KB Output is correct
96 Correct 2452 ms 59852 KB Output is correct
97 Correct 1191 ms 52076 KB Output is correct
98 Correct 1242 ms 58720 KB Output is correct
99 Correct 2407 ms 58060 KB Output is correct
100 Correct 2396 ms 57580 KB Output is correct
101 Correct 2564 ms 58140 KB Output is correct
102 Correct 2452 ms 58292 KB Output is correct
103 Correct 2653 ms 60840 KB Output is correct
104 Correct 2684 ms 60220 KB Output is correct
105 Correct 1997 ms 60000 KB Output is correct
106 Correct 1572 ms 59892 KB Output is correct
107 Correct 1862 ms 53476 KB Output is correct
108 Correct 2568 ms 57852 KB Output is correct
109 Correct 1833 ms 54672 KB Output is correct