oj.uz

Submission #711201

# Submission time Handle Problem Language Result Execution time Memory
711201 2023-03-16T09:46:32 Z sysia Inside information (BOI21_servers) C++17
100 / 100
 1075 ms 121392 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
using namespace __gnu_pbds;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 20;
typedef tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//czy sciezka od a do b uzywa krawedzi ≤t i jest rosnaca??
struct Q{
	int a, b, t, idx; 
	Q(){}
	Q(int _a, int _b, int _t, int _idx){
		a = _a, b = _b, t = _t, idx = _idx;
	}
};

struct DSU{
	vector<int>rep, sz;

	DSU(int n){
		rep.resize(n);
		iota(rep.begin(), rep.end(), 0);
		sz.assign(n, 1);
	}

	int f(int a){return a == rep[a] ? a : rep[a] = f(rep[a]);}

	bool sameset(int a, int b){
		return f(a) == f(b);
	}

	bool u(int a, int b){
		a = f(a); b = f(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		rep[b] = a;
		return true;
	}
};

void solve(){
    int n, q; cin >> n >> q;
    int m = 1, idx = 1;
    vector<Q>Qque;
	vector<int>ans(q+1);
	vector<vector<T>>g(n+1), event(n+1);
	vector<T>edges = {{0, 0}};
    for (int i = 1; i<n+q; i++){
		char c; cin >> c;
		if (c == 'S'){
			int a, b; cin >> a >> b;
			g[a].emplace_back(b, m);
			g[b].emplace_back(a, m);
			edges.emplace_back(a, b);
			m++;
		} else if (c == 'Q'){
			int a, b; cin >> a >> b;
			Qque.emplace_back(b, a, m, idx++);
		} else {
			int a; cin >> a;
			event[a].emplace_back(m-1, idx++);
		}
	}
	DSU dsu(n+2);
	vector up(n+1, vector<int>(K));
	vector mn(n+1, vector<int>(K, oo));
	vector mx(n+1, vector<int>(K, -oo));
	vector<int>depth(n+1), cost(n+1);
	function<void(int, int, int)>dfs = [&](int v, int pa, int c){
		up[v][0] = pa;
		cost[v] = c;
		for (int i = 1; i<K; i++) {
			up[v][i] = up[up[v][i-1]][i-1];
			mn[v][i] = min(mn[v][i-1], mn[up[v][i-1]][i-1]);
			mx[v][i] = max(mx[v][i-1], mx[up[v][i-1]][i-1]);
		}
		for (auto [x, id]: g[v]){
			if (x == pa) continue;
			depth[x] = depth[v]+1;
			mn[x][0] = id - c;
			mx[x][0] = id - c;
			dfs(x, v, id);
		}
	};
	dfs(1, 1, -oo);
	auto lca = [&](int a, int b){
		if (depth[a] > depth[b]) swap(a, b);
		for (int i = K-1; i>=0; i--){
			if (depth[b] - (1<<i) >= depth[a]){
				b = up[b][i];
			}
		}
		if (a == b) return a;
		for (int i = K-1; i>=0; i--){
			if (up[a][i] != up[b][i]){
				a = up[a][i];
				b = up[b][i];
			}
		}
		return up[a][0];
	};
	int ptr = 0;
	auto is_increasing = [&](int a, int b, bool f){ 
		//f = 1->chcemy by byla rosnaca w gore
		//f = 0->malejaca w gore
		if (depth[b] - depth[a] <= 1) return true;
		//sciezka pionowa od a do b (b w poddrzewie a)
		// debug(a, b, depth[a], depth[b]);
		int jump = depth[b] - depth[a] - 1;
		if (!f){
			int currmn = oo, v = b;
			for (int i = K-1; i>=0; i--){
				if (jump&(1<<i)){
					debug(i, v, mn[v][i]);
					currmn = min(currmn, mn[v][i]);
					v = up[v][i];
				}
			}
			return currmn > 0;
		}
		int currmx = -oo, v = b;
		for (int i = K-1; i>=0; i--){
			if (jump&(1<<i)){
				debug(i, v, mx[v][i]);
				currmx = max(currmx, mx[v][i]);
				v = up[v][i];
			}
		}
		debug(currmx);
		return currmx < 0;
	};
	auto below_lca = [&](int a, int b){
		bool f = 0;
		if (depth[a] < depth[b]) {
			swap(a, b);
			f = 1;
		}
		for (int i = K-1; i>=0; i--){
			if (depth[a] - (1<<i) >= depth[b]){
				a = up[a][i];
			}
		}
		assert(a != b);
		for (int i = K-1; i>=0; i--){
			if (up[a][i] != up[b][i]){
				a = up[a][i];
				b = up[b][i];
			}
		}
		if (f) swap(a, b);
		return T{a, b};
	};
	for (auto [a, b, t, id]: Qque){
		while (ptr + 1 < t){
			ptr++;
			dsu.u(edges[ptr].first, edges[ptr].second);
		}
		if (!dsu.sameset(a, b)) {
			ans[id] = -2;
			// cout << "no\n";
			continue;
		}
		int l = lca(a, b);
		debug(a, b, l);
		if (l == b){
			//sciezka ma byc rosnaca
			if (is_increasing(b, a, 1)) ans[id] = -1;
			else ans[id] = -2;
			continue;
		} 
		if (l == a){
			//sciezka ma byc malejaca
			if (is_increasing(a, b, 0)) ans[id] = -1;
			else ans[id] = -2;
			continue;
		}
		//rosnaca od a do l i malejaca od l do b
		T now = below_lca(a, b);
		debug(now, is_increasing(l, a, 1), is_increasing(l, b, 0));
		if (is_increasing(l, a, 1) && is_increasing(l, b, 0) && cost[now.first] < cost[now.second]) ans[id] = -1;
		else ans[id] = -2;
	}

	//-1 ->yes
	//-2 ->no

	vector<int>sub(n+1), used(n+1);
	function<int(int, int)>subsize = [&](int v, int pa){
		sub[v] = 1;
		for (auto [x, id]: g[v]){
			if (x == pa || used[x]) continue;
			sub[v] += subsize(x, v);
		}
		return sub[v];
	};
	function<int(int, int, int)>get_centroid = [&](int v, int pa, int ms){
		for (auto [x, id]: g[v]){
			if (x == pa || used[x]) continue;
			if (2*sub[x] > ms) return get_centroid(x, v, ms);
		}
		return v;
	};
	vector<int>valid, tmp;
	vector<bool>increasing(n+1), decreasing(n+1);
	vector<int> cost2(n+1);
	function<void(int, int, int, bool, bool)>dfessa = [&](int v, int pa, int c, bool inc, bool dec){
		increasing[v] = inc;
		decreasing[v] = dec;
		cost2[v] = c;
		valid.emplace_back(v);
		tmp.emplace_back(v);
		for (auto [x, id]: g[v]){
			if (x == pa || used[x]) continue;
			dfessa(x, v, id, (inc && id > c), (dec && (id < c)));
		}	
	};
	function<void(int)>centroid = [&](int v){
		v = get_centroid(v, v, subsize(v, v));
		sort(g[v].begin(), g[v].end(), [&](auto x, auto y){return x.second > y.second;});
		debug(v);
		ordered_set now;
		for (auto [y, tttt]: g[v]){
			if (used[y]) continue;
			dfessa(y, v, tttt, 1, 1);
			for (auto x: tmp){
				if (!decreasing[x]) continue;
				for (auto [czas, id]: event[x]){
					if (x == v)	continue;
					if (cost2[y] > czas) continue;
					int it = now.order_of_key({czas, oo});
					debug(x, czas, id, it+1);
					ans[id] += it+1;
				}
			}
			debug(y, tmp);
			for (auto x: tmp){
				debug(x, cost2[x]);
				if (increasing[x]) now.insert({cost2[x], x}); //remember about centroid +1 !!
				debug(x, (bool)increasing[x], (bool)decreasing[x]);
			}
			tmp.clear();
		}
		debug(now);
		for (auto [czas, id]: event[v]){
			int it = now.order_of_key({czas, oo});
			debug(v, czas, id, it+1);
			ans[id] += it+1;
		}
		for (auto x: valid){
			increasing[x] = 0;
			decreasing[x] = 0;
		}
		valid.clear();
		// exit(0);
		used[v] = 1;
		for (auto [x, id]: g[v]){
			if (!used[x]){
				centroid(x);
			}
		}
	};
	centroid(1);
	for (int i = 1; i<=q; i++){
		if (ans[i] == -1) cout << "yes\n";
		if (ans[i] == -2) cout << "no\n";
		if (ans[i] >= 0) cout << ans[i] << "\n";
	}
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5448 KB Output is correct
2 Correct 55 ms 8432 KB Output is correct
3 Correct 58 ms 8636 KB Output is correct
4 Correct 50 ms 8592 KB Output is correct
5 Correct 98 ms 8964 KB Output is correct
6 Correct 59 ms 8660 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5448 KB Output is correct
2 Correct 55 ms 8432 KB Output is correct
3 Correct 58 ms 8636 KB Output is correct
4 Correct 50 ms 8592 KB Output is correct
5 Correct 98 ms 8964 KB Output is correct
6 Correct 59 ms 8660 KB Output is correct
7 Correct 30 ms 5420 KB Output is correct
8 Correct 60 ms 9072 KB Output is correct
9 Correct 50 ms 8940 KB Output is correct
10 Correct 56 ms 9276 KB Output is correct
11 Correct 100 ms 9656 KB Output is correct
12 Correct 45 ms 8984 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5496 KB Output is correct
2 Correct 444 ms 104132 KB Output is correct
3 Correct 365 ms 104068 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5496 KB Output is correct
2 Correct 444 ms 104132 KB Output is correct
3 Correct 365 ms 104068 KB Output is correct
4 Correct 41 ms 5452 KB Output is correct
5 Correct 415 ms 103868 KB Output is correct
6 Correct 333 ms 102540 KB Output is correct
7 Correct 324 ms 102496 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5504 KB Output is correct
2 Correct 555 ms 113568 KB Output is correct
3 Correct 518 ms 113568 KB Output is correct
4 Correct 643 ms 119576 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5504 KB Output is correct
2 Correct 555 ms 113568 KB Output is correct
3 Correct 518 ms 113568 KB Output is correct
4 Correct 643 ms 119576 KB Output is correct
5 Correct 36 ms 5464 KB Output is correct
6 Correct 595 ms 116396 KB Output is correct
7 Correct 604 ms 121364 KB Output is correct
8 Correct 575 ms 115716 KB Output is correct
9 Correct 637 ms 115764 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5456 KB Output is correct
2 Correct 518 ms 107512 KB Output is correct
3 Correct 458 ms 99440 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5456 KB Output is correct
2 Correct 518 ms 107512 KB Output is correct
3 Correct 458 ms 99440 KB Output is correct
4 Correct 35 ms 5408 KB Output is correct
5 Correct 536 ms 110180 KB Output is correct
6 Correct 477 ms 101896 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5448 KB Output is correct
2 Correct 602 ms 113596 KB Output is correct
3 Correct 509 ms 113564 KB Output is correct
4 Correct 623 ms 119540 KB Output is correct
5 Correct 28 ms 5448 KB Output is correct
6 Correct 588 ms 107476 KB Output is correct
7 Correct 430 ms 99468 KB Output is correct
8 Correct 642 ms 100132 KB Output is correct
9 Correct 581 ms 100212 KB Output is correct
10 Correct 785 ms 107760 KB Output is correct
11 Correct 921 ms 106484 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5448 KB Output is correct
2 Correct 602 ms 113596 KB Output is correct
3 Correct 509 ms 113564 KB Output is correct
4 Correct 623 ms 119540 KB Output is correct
5 Correct 28 ms 5448 KB Output is correct
6 Correct 588 ms 107476 KB Output is correct
7 Correct 430 ms 99468 KB Output is correct
8 Correct 642 ms 100132 KB Output is correct
9 Correct 581 ms 100212 KB Output is correct
10 Correct 785 ms 107760 KB Output is correct
11 Correct 921 ms 106484 KB Output is correct
12 Correct 30 ms 5452 KB Output is correct
13 Correct 591 ms 116452 KB Output is correct
14 Correct 673 ms 121392 KB Output is correct
15 Correct 591 ms 115712 KB Output is correct
16 Correct 578 ms 115728 KB Output is correct
17 Correct 45 ms 6232 KB Output is correct
18 Correct 499 ms 110140 KB Output is correct
19 Correct 535 ms 101896 KB Output is correct
20 Correct 648 ms 102344 KB Output is correct
21 Correct 605 ms 102720 KB Output is correct
22 Correct 838 ms 107776 KB Output is correct
23 Correct 1075 ms 112224 KB Output is correct
24 Correct 967 ms 113072 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5452 KB Output is correct
2 Correct 51 ms 8460 KB Output is correct
3 Correct 63 ms 8572 KB Output is correct
4 Correct 46 ms 8688 KB Output is correct
5 Correct 75 ms 8964 KB Output is correct
6 Correct 51 ms 8708 KB Output is correct
7 Correct 32 ms 5448 KB Output is correct
8 Correct 399 ms 104048 KB Output is correct
9 Correct 461 ms 104096 KB Output is correct
10 Correct 40 ms 5448 KB Output is correct
11 Correct 564 ms 113620 KB Output is correct
12 Correct 617 ms 113568 KB Output is correct
13 Correct 658 ms 119528 KB Output is correct
14 Correct 27 ms 5516 KB Output is correct
15 Correct 594 ms 107512 KB Output is correct
16 Correct 485 ms 99432 KB Output is correct
17 Correct 682 ms 100176 KB Output is correct
18 Correct 490 ms 100244 KB Output is correct
19 Correct 788 ms 107788 KB Output is correct
20 Correct 898 ms 106464 KB Output is correct
21 Correct 402 ms 107124 KB Output is correct
22 Correct 375 ms 103400 KB Output is correct
23 Correct 456 ms 98912 KB Output is correct
24 Correct 472 ms 99228 KB Output is correct
25 Correct 642 ms 110932 KB Output is correct
26 Correct 473 ms 98476 KB Output is correct
27 Correct 422 ms 98508 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5452 KB Output is correct
2 Correct 51 ms 8460 KB Output is correct
3 Correct 63 ms 8572 KB Output is correct
4 Correct 46 ms 8688 KB Output is correct
5 Correct 75 ms 8964 KB Output is correct
6 Correct 51 ms 8708 KB Output is correct
7 Correct 32 ms 5448 KB Output is correct
8 Correct 399 ms 104048 KB Output is correct
9 Correct 461 ms 104096 KB Output is correct
10 Correct 40 ms 5448 KB Output is correct
11 Correct 564 ms 113620 KB Output is correct
12 Correct 617 ms 113568 KB Output is correct
13 Correct 658 ms 119528 KB Output is correct
14 Correct 27 ms 5516 KB Output is correct
15 Correct 594 ms 107512 KB Output is correct
16 Correct 485 ms 99432 KB Output is correct
17 Correct 682 ms 100176 KB Output is correct
18 Correct 490 ms 100244 KB Output is correct
19 Correct 788 ms 107788 KB Output is correct
20 Correct 898 ms 106464 KB Output is correct
21 Correct 402 ms 107124 KB Output is correct
22 Correct 375 ms 103400 KB Output is correct
23 Correct 456 ms 98912 KB Output is correct
24 Correct 472 ms 99228 KB Output is correct
25 Correct 642 ms 110932 KB Output is correct
26 Correct 473 ms 98476 KB Output is correct
27 Correct 422 ms 98508 KB Output is correct
28 Correct 24 ms 5452 KB Output is correct
29 Correct 45 ms 9100 KB Output is correct
30 Correct 47 ms 9024 KB Output is correct
31 Correct 50 ms 9264 KB Output is correct
32 Correct 56 ms 9600 KB Output is correct
33 Correct 41 ms 8988 KB Output is correct
34 Correct 30 ms 6300 KB Output is correct
35 Correct 412 ms 106576 KB Output is correct
36 Correct 320 ms 104184 KB Output is correct
37 Correct 353 ms 104336 KB Output is correct
38 Correct 35 ms 6220 KB Output is correct
39 Correct 629 ms 116404 KB Output is correct
40 Correct 610 ms 121384 KB Output is correct
41 Correct 610 ms 115800 KB Output is correct
42 Correct 617 ms 115732 KB Output is correct
43 Correct 27 ms 6220 KB Output is correct
44 Correct 521 ms 110100 KB Output is correct
45 Correct 463 ms 101980 KB Output is correct
46 Correct 561 ms 102456 KB Output is correct
47 Correct 532 ms 102732 KB Output is correct
48 Correct 677 ms 107700 KB Output is correct
49 Correct 954 ms 112340 KB Output is correct
50 Correct 799 ms 113036 KB Output is correct
51 Correct 391 ms 109352 KB Output is correct
52 Correct 311 ms 105132 KB Output is correct
53 Correct 301 ms 104760 KB Output is correct
54 Correct 287 ms 105292 KB Output is correct
55 Correct 342 ms 105720 KB Output is correct
56 Correct 363 ms 100936 KB Output is correct
57 Correct 598 ms 110900 KB Output is correct
58 Correct 579 ms 100840 KB Output is correct
59 Correct 407 ms 101800 KB Output is correct