oj.uz

Submission #711205

# Submission time Handle Problem Language Result Execution time Memory
711205 2023-03-16T09:51:51 Z sysia Inside information (BOI21_servers) C++17
100 / 100
 806 ms 78260 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

typedef pair<int, int> T;
const int oo = 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>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;
		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)));
		}	
	};
	ordered_set now;
	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;});
		now.clear();
		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 || 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;
		}
		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 24 ms 3272 KB Output is correct
2 Correct 33 ms 5052 KB Output is correct
3 Correct 47 ms 5180 KB Output is correct
4 Correct 34 ms 5220 KB Output is correct
5 Correct 70 ms 5544 KB Output is correct
6 Correct 44 ms 5264 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3272 KB Output is correct
2 Correct 33 ms 5052 KB Output is correct
3 Correct 47 ms 5180 KB Output is correct
4 Correct 34 ms 5220 KB Output is correct
5 Correct 70 ms 5544 KB Output is correct
6 Correct 44 ms 5264 KB Output is correct
7 Correct 25 ms 3072 KB Output is correct
8 Correct 41 ms 4924 KB Output is correct
9 Correct 44 ms 4968 KB Output is correct
10 Correct 36 ms 5000 KB Output is correct
11 Correct 53 ms 5480 KB Output is correct
12 Correct 46 ms 5184 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3312 KB Output is correct
2 Correct 336 ms 67552 KB Output is correct
3 Correct 351 ms 67596 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3312 KB Output is correct
2 Correct 336 ms 67552 KB Output is correct
3 Correct 351 ms 67596 KB Output is correct
4 Correct 33 ms 3204 KB Output is correct
5 Correct 311 ms 67560 KB Output is correct
6 Correct 306 ms 66900 KB Output is correct
7 Correct 270 ms 66788 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3268 KB Output is correct
2 Correct 413 ms 74648 KB Output is correct
3 Correct 417 ms 74620 KB Output is correct
4 Correct 510 ms 78012 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3268 KB Output is correct
2 Correct 413 ms 74648 KB Output is correct
3 Correct 417 ms 74620 KB Output is correct
4 Correct 510 ms 78012 KB Output is correct
5 Correct 24 ms 3140 KB Output is correct
6 Correct 468 ms 75204 KB Output is correct
7 Correct 489 ms 77876 KB Output is correct
8 Correct 479 ms 75200 KB Output is correct
9 Correct 494 ms 75180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3180 KB Output is correct
2 Correct 483 ms 63616 KB Output is correct
3 Correct 313 ms 61060 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3180 KB Output is correct
2 Correct 483 ms 63616 KB Output is correct
3 Correct 313 ms 61060 KB Output is correct
4 Correct 27 ms 3096 KB Output is correct
5 Correct 443 ms 64384 KB Output is correct
6 Correct 410 ms 61212 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3232 KB Output is correct
2 Correct 524 ms 74584 KB Output is correct
3 Correct 456 ms 74640 KB Output is correct
4 Correct 513 ms 78260 KB Output is correct
5 Correct 25 ms 3264 KB Output is correct
6 Correct 432 ms 63680 KB Output is correct
7 Correct 314 ms 60988 KB Output is correct
8 Correct 442 ms 61420 KB Output is correct
9 Correct 433 ms 61404 KB Output is correct
10 Correct 553 ms 68760 KB Output is correct
11 Correct 659 ms 67636 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3232 KB Output is correct
2 Correct 524 ms 74584 KB Output is correct
3 Correct 456 ms 74640 KB Output is correct
4 Correct 513 ms 78260 KB Output is correct
5 Correct 25 ms 3264 KB Output is correct
6 Correct 432 ms 63680 KB Output is correct
7 Correct 314 ms 60988 KB Output is correct
8 Correct 442 ms 61420 KB Output is correct
9 Correct 433 ms 61404 KB Output is correct
10 Correct 553 ms 68760 KB Output is correct
11 Correct 659 ms 67636 KB Output is correct
12 Correct 25 ms 3076 KB Output is correct
13 Correct 442 ms 75292 KB Output is correct
14 Correct 469 ms 77876 KB Output is correct
15 Correct 464 ms 75296 KB Output is correct
16 Correct 505 ms 75280 KB Output is correct
17 Correct 23 ms 3268 KB Output is correct
18 Correct 438 ms 64380 KB Output is correct
19 Correct 361 ms 61220 KB Output is correct
20 Correct 450 ms 62100 KB Output is correct
21 Correct 466 ms 61996 KB Output is correct
22 Correct 613 ms 67052 KB Output is correct
23 Correct 803 ms 68908 KB Output is correct
24 Correct 734 ms 68984 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3180 KB Output is correct
2 Correct 35 ms 5024 KB Output is correct
3 Correct 43 ms 5072 KB Output is correct
4 Correct 37 ms 5172 KB Output is correct
5 Correct 56 ms 5432 KB Output is correct
6 Correct 45 ms 5296 KB Output is correct
7 Correct 24 ms 3312 KB Output is correct
8 Correct 349 ms 67584 KB Output is correct
9 Correct 329 ms 67708 KB Output is correct
10 Correct 22 ms 3264 KB Output is correct
11 Correct 461 ms 74656 KB Output is correct
12 Correct 434 ms 74640 KB Output is correct
13 Correct 534 ms 78104 KB Output is correct
14 Correct 23 ms 3172 KB Output is correct
15 Correct 442 ms 63696 KB Output is correct
16 Correct 372 ms 61004 KB Output is correct
17 Correct 456 ms 61340 KB Output is correct
18 Correct 412 ms 61412 KB Output is correct
19 Correct 596 ms 68684 KB Output is correct
20 Correct 640 ms 67568 KB Output is correct
21 Correct 319 ms 66520 KB Output is correct
22 Correct 328 ms 64176 KB Output is correct
23 Correct 341 ms 61044 KB Output is correct
24 Correct 357 ms 61032 KB Output is correct
25 Correct 535 ms 70164 KB Output is correct
26 Correct 371 ms 60288 KB Output is correct
27 Correct 332 ms 60340 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3180 KB Output is correct
2 Correct 35 ms 5024 KB Output is correct
3 Correct 43 ms 5072 KB Output is correct
4 Correct 37 ms 5172 KB Output is correct
5 Correct 56 ms 5432 KB Output is correct
6 Correct 45 ms 5296 KB Output is correct
7 Correct 24 ms 3312 KB Output is correct
8 Correct 349 ms 67584 KB Output is correct
9 Correct 329 ms 67708 KB Output is correct
10 Correct 22 ms 3264 KB Output is correct
11 Correct 461 ms 74656 KB Output is correct
12 Correct 434 ms 74640 KB Output is correct
13 Correct 534 ms 78104 KB Output is correct
14 Correct 23 ms 3172 KB Output is correct
15 Correct 442 ms 63696 KB Output is correct
16 Correct 372 ms 61004 KB Output is correct
17 Correct 456 ms 61340 KB Output is correct
18 Correct 412 ms 61412 KB Output is correct
19 Correct 596 ms 68684 KB Output is correct
20 Correct 640 ms 67568 KB Output is correct
21 Correct 319 ms 66520 KB Output is correct
22 Correct 328 ms 64176 KB Output is correct
23 Correct 341 ms 61044 KB Output is correct
24 Correct 357 ms 61032 KB Output is correct
25 Correct 535 ms 70164 KB Output is correct
26 Correct 371 ms 60288 KB Output is correct
27 Correct 332 ms 60340 KB Output is correct
28 Correct 23 ms 3136 KB Output is correct
29 Correct 35 ms 4940 KB Output is correct
30 Correct 38 ms 4960 KB Output is correct
31 Correct 49 ms 5040 KB Output is correct
32 Correct 56 ms 5380 KB Output is correct
33 Correct 41 ms 5192 KB Output is correct
34 Correct 24 ms 3320 KB Output is correct
35 Correct 341 ms 67624 KB Output is correct
36 Correct 296 ms 67172 KB Output is correct
37 Correct 329 ms 66928 KB Output is correct
38 Correct 23 ms 3304 KB Output is correct
39 Correct 419 ms 75236 KB Output is correct
40 Correct 533 ms 77744 KB Output is correct
41 Correct 501 ms 75296 KB Output is correct
42 Correct 460 ms 75176 KB Output is correct
43 Correct 32 ms 3236 KB Output is correct
44 Correct 413 ms 64536 KB Output is correct
45 Correct 363 ms 61044 KB Output is correct
46 Correct 436 ms 61740 KB Output is correct
47 Correct 438 ms 61932 KB Output is correct
48 Correct 607 ms 66892 KB Output is correct
49 Correct 806 ms 68828 KB Output is correct
50 Correct 716 ms 68852 KB Output is correct
51 Correct 300 ms 66992 KB Output is correct
52 Correct 301 ms 66864 KB Output is correct
53 Correct 266 ms 66780 KB Output is correct
54 Correct 312 ms 66972 KB Output is correct
55 Correct 271 ms 63580 KB Output is correct
56 Correct 386 ms 60588 KB Output is correct
57 Correct 504 ms 69252 KB Output is correct
58 Correct 431 ms 60896 KB Output is correct
59 Correct 387 ms 60472 KB Output is correct