oj.uz

Submission #635041

# Submission time Handle Problem Language Result Execution time Memory
635041 2022-08-25T10:42:02 Z IWTIM Bridges (APIO19_bridges) C++14
100 / 100
 2290 ms 233728 KB 
# include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
const int MX = 2e5+5;
const ll BIG = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
 
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
const int N = 3e5 + 5, B = 700;
int sz[N],n,m,a[N],b[N],c[N],x[N],y[N],ty[N],q;
int p[N], cur[N], fix[N],ans[N];
vector <int> toadd[N];
vector < pii > upd, que,con;
stack < pair <pii, pii > > st;
int get_col(int a) {
	if (a == p[a]) return a;
	else return get_col(p[a]);
}
void col(int a, int b) {
    //cout<<"col  "<<a<<" "<<b<<"\n";
	a = get_col(a);
	b = get_col(b);
	
	if (sz[a] < sz[b]) swap(a,b);
	if (a == b) return ;
	st.push({{a,b},{sz[a],sz[b]}});
	sz[a] += sz[b];
	sz[b] = 0;
	p[b] = a;
}
void rollback(int szz) {
	while (st.size() > szz) {
		auto x = st.top();
		st.pop();
		int a = x.f.f, b = x.f.s, sza = x.s.f, szb = x.s.s; 
		sz[a] = sza; sz[b] = szb; p[a] = a; p[b] = b;
	}
}
void init() {
	for (int i = 1; i <= max(n,m); i++) {
		fix[i] = 0; sz[i] = 1; p[i] = i;
	}
	con.clear(); upd.clear(); que.clear();
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (int i = 1; i <= m; i++) {
		cin>>a[i]>>b[i]>>c[i];
	}
	cin>>q;
	for (int i = 1; i <= q; i++) {
		cin>>ty[i]>>x[i]>>y[i];
	}
	init();
	for (int le = 1; le <= q; le += B) {
		int ri = min(le + B - 1, q);
		for (int i = le; i <= ri; i++) {
			if (ty[i] == 1) {
				upd.pb({y[i], x[i]});
				fix[x[i]] = 1;
			} else {
				que.pb({y[i], i});
			}
		} 
		for (int i = 1; i <= m; i++) {
			if (!fix[i]) con.pb({c[i], i});
			cur[i] = c[i];
		}
		for (int i = le; i <= ri; i++) {
		    if (ty[i] == 1) c[x[i]] = y[i];
		}
		for (int i = le; i <= ri; i++) {
			if (ty[i] == 1) {
				cur[x[i]] = y[i];
			} else {
				for (auto id : upd) {
					if (cur[id.s] >= y[i]) toadd[i].pb(id.s);// add and rollback
				}
			}
		}
		sort(que.rbegin(),que.rend());
		sort(con.rbegin(),con.rend());
		int curid = 0;
		for (int i = 0; i < que.size(); i++) {
			while (curid < con.size() && con[curid].f >= que[i].f) {
				col(a[con[curid].s], b[con[curid].s]);
				curid++;
			}
			int szz = st.size();
			for (int id : toadd[que[i].s]) {
				col(a[id],b[id]);
			}
			ans[que[i].s] = sz[get_col(x[que[i].s])];
			rollback(szz);
		}
		init();
	}
	for (int i = 1; i <= q; i++) {
		if (ty[i] == 2) cout<<ans[i]<<"\n";
	}
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:204:19: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  204 |  while (st.size() > szz) {
      |         ~~~~~~~~~~^~~~~
bridges.cpp: At global scope:
bridges.cpp:217:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  217 | main() {
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:257:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |   for (int i = 0; i < que.size(); i++) {
      |                   ~~^~~~~~~~~~~~
bridges.cpp:258:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |    while (curid < con.size() && con[curid].f >= que[i].f) {
      |           ~~~~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7444 KB Output is correct
3 Correct 31 ms 12556 KB Output is correct
4 Correct 9 ms 7600 KB Output is correct
5 Correct 37 ms 13584 KB Output is correct
6 Correct 35 ms 13388 KB Output is correct
7 Correct 32 ms 13388 KB Output is correct
8 Correct 42 ms 12220 KB Output is correct
9 Correct 34 ms 17480 KB Output is correct
10 Correct 34 ms 12896 KB Output is correct
11 Correct 37 ms 12500 KB Output is correct
12 Correct 39 ms 14284 KB Output is correct
13 Correct 38 ms 13160 KB Output is correct
14 Correct 43 ms 12500 KB Output is correct
15 Correct 38 ms 12936 KB Output is correct
16 Correct 34 ms 14952 KB Output is correct
17 Correct 32 ms 13784 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1451 ms 178692 KB Output is correct
2 Correct 1366 ms 178596 KB Output is correct
3 Correct 1419 ms 178768 KB Output is correct
4 Correct 1469 ms 178632 KB Output is correct
5 Correct 1493 ms 178832 KB Output is correct
6 Correct 1844 ms 228156 KB Output is correct
7 Correct 1804 ms 228600 KB Output is correct
8 Correct 1849 ms 228336 KB Output is correct
9 Correct 39 ms 9172 KB Output is correct
10 Correct 1328 ms 203112 KB Output is correct
11 Correct 1262 ms 187796 KB Output is correct
12 Correct 1284 ms 169604 KB Output is correct
13 Correct 1375 ms 166820 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 138024 KB Output is correct
2 Correct 684 ms 104276 KB Output is correct
3 Correct 1327 ms 162816 KB Output is correct
4 Correct 1264 ms 137664 KB Output is correct
5 Correct 40 ms 9164 KB Output is correct
6 Correct 1257 ms 153952 KB Output is correct
7 Correct 1092 ms 130652 KB Output is correct
8 Correct 996 ms 118296 KB Output is correct
9 Correct 878 ms 110872 KB Output is correct
10 Correct 833 ms 103148 KB Output is correct
11 Correct 982 ms 108832 KB Output is correct
12 Correct 813 ms 100172 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2222 ms 128712 KB Output is correct
2 Correct 48 ms 10452 KB Output is correct
3 Correct 218 ms 13104 KB Output is correct
4 Correct 145 ms 13216 KB Output is correct
5 Correct 2102 ms 131000 KB Output is correct
6 Correct 2251 ms 132568 KB Output is correct
7 Correct 2190 ms 131076 KB Output is correct
8 Correct 1102 ms 130644 KB Output is correct
9 Correct 1031 ms 130796 KB Output is correct
10 Correct 1052 ms 130804 KB Output is correct
11 Correct 1655 ms 132304 KB Output is correct
12 Correct 1653 ms 132380 KB Output is correct
13 Correct 1665 ms 132244 KB Output is correct
14 Correct 1846 ms 131096 KB Output is correct
15 Correct 1895 ms 131008 KB Output is correct
16 Correct 2106 ms 133168 KB Output is correct
17 Correct 2195 ms 133056 KB Output is correct
18 Correct 2165 ms 133836 KB Output is correct
19 Correct 1982 ms 133968 KB Output is correct
20 Correct 1649 ms 132796 KB Output is correct
21 Correct 1666 ms 132748 KB Output is correct
22 Correct 1899 ms 130796 KB Output is correct
23 Correct 1753 ms 119296 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1451 ms 178692 KB Output is correct
2 Correct 1366 ms 178596 KB Output is correct
3 Correct 1419 ms 178768 KB Output is correct
4 Correct 1469 ms 178632 KB Output is correct
5 Correct 1493 ms 178832 KB Output is correct
6 Correct 1844 ms 228156 KB Output is correct
7 Correct 1804 ms 228600 KB Output is correct
8 Correct 1849 ms 228336 KB Output is correct
9 Correct 39 ms 9172 KB Output is correct
10 Correct 1328 ms 203112 KB Output is correct
11 Correct 1262 ms 187796 KB Output is correct
12 Correct 1284 ms 169604 KB Output is correct
13 Correct 1375 ms 166820 KB Output is correct
14 Correct 1121 ms 138024 KB Output is correct
15 Correct 684 ms 104276 KB Output is correct
16 Correct 1327 ms 162816 KB Output is correct
17 Correct 1264 ms 137664 KB Output is correct
18 Correct 40 ms 9164 KB Output is correct
19 Correct 1257 ms 153952 KB Output is correct
20 Correct 1092 ms 130652 KB Output is correct
21 Correct 996 ms 118296 KB Output is correct
22 Correct 878 ms 110872 KB Output is correct
23 Correct 833 ms 103148 KB Output is correct
24 Correct 982 ms 108832 KB Output is correct
25 Correct 813 ms 100172 KB Output is correct
26 Correct 1331 ms 178664 KB Output is correct
27 Correct 1614 ms 204240 KB Output is correct
28 Correct 1428 ms 177572 KB Output is correct
29 Correct 1162 ms 144260 KB Output is correct
30 Correct 1561 ms 192440 KB Output is correct
31 Correct 1596 ms 194556 KB Output is correct
32 Correct 1579 ms 195192 KB Output is correct
33 Correct 1412 ms 176868 KB Output is correct
34 Correct 1415 ms 177420 KB Output is correct
35 Correct 1420 ms 177328 KB Output is correct
36 Correct 1173 ms 149272 KB Output is correct
37 Correct 1229 ms 148192 KB Output is correct
38 Correct 1171 ms 146924 KB Output is correct
39 Correct 1062 ms 136172 KB Output is correct
40 Correct 1048 ms 135748 KB Output is correct
41 Correct 1110 ms 135168 KB Output is correct
42 Correct 996 ms 129120 KB Output is correct
43 Correct 1016 ms 129488 KB Output is correct
44 Correct 998 ms 127988 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7444 KB Output is correct
3 Correct 31 ms 12556 KB Output is correct
4 Correct 9 ms 7600 KB Output is correct
5 Correct 37 ms 13584 KB Output is correct
6 Correct 35 ms 13388 KB Output is correct
7 Correct 32 ms 13388 KB Output is correct
8 Correct 42 ms 12220 KB Output is correct
9 Correct 34 ms 17480 KB Output is correct
10 Correct 34 ms 12896 KB Output is correct
11 Correct 37 ms 12500 KB Output is correct
12 Correct 39 ms 14284 KB Output is correct
13 Correct 38 ms 13160 KB Output is correct
14 Correct 43 ms 12500 KB Output is correct
15 Correct 38 ms 12936 KB Output is correct
16 Correct 34 ms 14952 KB Output is correct
17 Correct 32 ms 13784 KB Output is correct
18 Correct 1451 ms 178692 KB Output is correct
19 Correct 1366 ms 178596 KB Output is correct
20 Correct 1419 ms 178768 KB Output is correct
21 Correct 1469 ms 178632 KB Output is correct
22 Correct 1493 ms 178832 KB Output is correct
23 Correct 1844 ms 228156 KB Output is correct
24 Correct 1804 ms 228600 KB Output is correct
25 Correct 1849 ms 228336 KB Output is correct
26 Correct 39 ms 9172 KB Output is correct
27 Correct 1328 ms 203112 KB Output is correct
28 Correct 1262 ms 187796 KB Output is correct
29 Correct 1284 ms 169604 KB Output is correct
30 Correct 1375 ms 166820 KB Output is correct
31 Correct 1121 ms 138024 KB Output is correct
32 Correct 684 ms 104276 KB Output is correct
33 Correct 1327 ms 162816 KB Output is correct
34 Correct 1264 ms 137664 KB Output is correct
35 Correct 40 ms 9164 KB Output is correct
36 Correct 1257 ms 153952 KB Output is correct
37 Correct 1092 ms 130652 KB Output is correct
38 Correct 996 ms 118296 KB Output is correct
39 Correct 878 ms 110872 KB Output is correct
40 Correct 833 ms 103148 KB Output is correct
41 Correct 982 ms 108832 KB Output is correct
42 Correct 813 ms 100172 KB Output is correct
43 Correct 2222 ms 128712 KB Output is correct
44 Correct 48 ms 10452 KB Output is correct
45 Correct 218 ms 13104 KB Output is correct
46 Correct 145 ms 13216 KB Output is correct
47 Correct 2102 ms 131000 KB Output is correct
48 Correct 2251 ms 132568 KB Output is correct
49 Correct 2190 ms 131076 KB Output is correct
50 Correct 1102 ms 130644 KB Output is correct
51 Correct 1031 ms 130796 KB Output is correct
52 Correct 1052 ms 130804 KB Output is correct
53 Correct 1655 ms 132304 KB Output is correct
54 Correct 1653 ms 132380 KB Output is correct
55 Correct 1665 ms 132244 KB Output is correct
56 Correct 1846 ms 131096 KB Output is correct
57 Correct 1895 ms 131008 KB Output is correct
58 Correct 2106 ms 133168 KB Output is correct
59 Correct 2195 ms 133056 KB Output is correct
60 Correct 2165 ms 133836 KB Output is correct
61 Correct 1982 ms 133968 KB Output is correct
62 Correct 1649 ms 132796 KB Output is correct
63 Correct 1666 ms 132748 KB Output is correct
64 Correct 1899 ms 130796 KB Output is correct
65 Correct 1753 ms 119296 KB Output is correct
66 Correct 1331 ms 178664 KB Output is correct
67 Correct 1614 ms 204240 KB Output is correct
68 Correct 1428 ms 177572 KB Output is correct
69 Correct 1162 ms 144260 KB Output is correct
70 Correct 1561 ms 192440 KB Output is correct
71 Correct 1596 ms 194556 KB Output is correct
72 Correct 1579 ms 195192 KB Output is correct
73 Correct 1412 ms 176868 KB Output is correct
74 Correct 1415 ms 177420 KB Output is correct
75 Correct 1420 ms 177328 KB Output is correct
76 Correct 1173 ms 149272 KB Output is correct
77 Correct 1229 ms 148192 KB Output is correct
78 Correct 1171 ms 146924 KB Output is correct
79 Correct 1062 ms 136172 KB Output is correct
80 Correct 1048 ms 135748 KB Output is correct
81 Correct 1110 ms 135168 KB Output is correct
82 Correct 996 ms 129120 KB Output is correct
83 Correct 1016 ms 129488 KB Output is correct
84 Correct 998 ms 127988 KB Output is correct
85 Correct 2223 ms 184524 KB Output is correct
86 Correct 216 ms 18312 KB Output is correct
87 Correct 174 ms 23052 KB Output is correct
88 Correct 2109 ms 194964 KB Output is correct
89 Correct 2214 ms 183320 KB Output is correct
90 Correct 2171 ms 196416 KB Output is correct
91 Correct 1417 ms 181456 KB Output is correct
92 Correct 1414 ms 181448 KB Output is correct
93 Correct 1807 ms 231160 KB Output is correct
94 Correct 1815 ms 184024 KB Output is correct
95 Correct 1828 ms 184024 KB Output is correct
96 Correct 2062 ms 232876 KB Output is correct
97 Correct 1988 ms 155656 KB Output is correct
98 Correct 2005 ms 154072 KB Output is correct
99 Correct 2227 ms 185880 KB Output is correct
100 Correct 2290 ms 185072 KB Output is correct
101 Correct 2290 ms 185240 KB Output is correct
102 Correct 2263 ms 185420 KB Output is correct
103 Correct 2255 ms 233728 KB Output is correct
104 Correct 2231 ms 233468 KB Output is correct
105 Correct 1860 ms 172804 KB Output is correct
106 Correct 1572 ms 152436 KB Output is correct
107 Correct 1806 ms 172712 KB Output is correct
108 Correct 2207 ms 221728 KB Output is correct
109 Correct 2143 ms 219752 KB Output is correct