oj.uz

Submission #710830

# Submission time Handle Problem Language Result Execution time Memory
710830 2023-03-15T21:54:20 Z sysia Inside information (BOI21_servers) C++17
50 / 100
 1309 ms 121448 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;
const int mod = 998244353;

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;
	}
};

//to be done
struct C{
	int v, t, idx;
	C(){}
	C(int _v, int _t, int _idx){
		v = _v, 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<C>Cque;
	vector<int>ans(q+1);
	vector<vector<T>>g(n+1);
	vector<T>edges = {{0, 0}};
	vector<vector<T>>event(n+1);
    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, 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);
	vector<int>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);
		}
	};
	for (auto [a, b]: edges){
		cerr << a << " " << b << "\n";
	}
	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;
	};
	for (int v = 1; v <= n; v++){
		debug(v, mn[v][0], mn[v][1]);
	}
	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;
	vector<bool>increasing(n+1), decreasing(n+1);
	vector<int> cnt(n+1), tmp;
	function<void(int, int, int, bool, bool)>dfessa = [&](int v, int pa, int c, bool inc, bool dec){
		increasing[v] = inc;
		decreasing[v] = dec;
		if (inc) cnt[v]++;
		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)));
			cnt[v] += cnt[x];
		}	
	};
	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 cost[x.first] > cost[y.first];});
		debug(v, g[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;
					}
					int it = now.order_of_key({czas, oo});
					debug(x, czas, id, cnt[x], it - (cnt[x] - 1) + 1);
					ans[id] += it+1;
				}
			}
			for (auto x: tmp){
				if (increasing[x] && x != v) now.insert({cost[x], x}); //remember about centroid +1 !!
				debug(x, (bool)increasing[x], (bool)decreasing[x]);
			}
			tmp.clear();
		}
		for (auto [czas, id]: event[v]){
			int it = now.order_of_key({czas, oo});
			debug(v, czas, id, it);
			ans[id] += it+1;
		}
		for (auto x: valid){
			increasing[x] = 0;
			decreasing[x] = 0;
			cnt[x] = 0;
		}
		valid.clear();
		debug(now);
		// exit(0);
		// valid.clear();
		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 28 ms 6072 KB Output is correct
2 Correct 58 ms 8872 KB Output is correct
3 Correct 66 ms 9008 KB Output is correct
4 Correct 53 ms 9012 KB Output is correct
5 Correct 77 ms 9320 KB Output is correct
6 Correct 65 ms 9148 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6072 KB Output is correct
2 Correct 58 ms 8872 KB Output is correct
3 Correct 66 ms 9008 KB Output is correct
4 Correct 53 ms 9012 KB Output is correct
5 Correct 77 ms 9320 KB Output is correct
6 Correct 65 ms 9148 KB Output is correct
7 Incorrect 29 ms 5832 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5984 KB Output is correct
2 Correct 941 ms 105372 KB Output is correct
3 Correct 942 ms 105400 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5984 KB Output is correct
2 Correct 941 ms 105372 KB Output is correct
3 Correct 942 ms 105400 KB Output is correct
4 Incorrect 27 ms 5708 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6008 KB Output is correct
2 Correct 1076 ms 115496 KB Output is correct
3 Correct 1063 ms 115484 KB Output is correct
4 Correct 1175 ms 121340 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6008 KB Output is correct
2 Correct 1076 ms 115496 KB Output is correct
3 Correct 1063 ms 115484 KB Output is correct
4 Correct 1175 ms 121340 KB Output is correct
5 Incorrect 25 ms 5708 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6056 KB Output is correct
2 Correct 1051 ms 109320 KB Output is correct
3 Correct 971 ms 101364 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6056 KB Output is correct
2 Correct 1051 ms 109320 KB Output is correct
3 Correct 971 ms 101364 KB Output is correct
4 Incorrect 25 ms 5788 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6016 KB Output is correct
2 Correct 1036 ms 115404 KB Output is correct
3 Correct 1010 ms 115416 KB Output is correct
4 Correct 1114 ms 121380 KB Output is correct
5 Correct 26 ms 5820 KB Output is correct
6 Correct 1008 ms 109372 KB Output is correct
7 Correct 944 ms 101324 KB Output is correct
8 Correct 1085 ms 102064 KB Output is correct
9 Correct 1055 ms 102096 KB Output is correct
10 Correct 1178 ms 109816 KB Output is correct
11 Correct 1295 ms 108332 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6016 KB Output is correct
2 Correct 1036 ms 115404 KB Output is correct
3 Correct 1010 ms 115416 KB Output is correct
4 Correct 1114 ms 121380 KB Output is correct
5 Correct 26 ms 5820 KB Output is correct
6 Correct 1008 ms 109372 KB Output is correct
7 Correct 944 ms 101324 KB Output is correct
8 Correct 1085 ms 102064 KB Output is correct
9 Correct 1055 ms 102096 KB Output is correct
10 Correct 1178 ms 109816 KB Output is correct
11 Correct 1295 ms 108332 KB Output is correct
12 Incorrect 23 ms 5756 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6004 KB Output is correct
2 Correct 55 ms 8916 KB Output is correct
3 Correct 65 ms 9092 KB Output is correct
4 Correct 60 ms 9120 KB Output is correct
5 Correct 90 ms 9344 KB Output is correct
6 Correct 65 ms 9072 KB Output is correct
7 Correct 30 ms 5920 KB Output is correct
8 Correct 883 ms 105412 KB Output is correct
9 Correct 903 ms 105500 KB Output is correct
10 Correct 24 ms 5844 KB Output is correct
11 Correct 1040 ms 115432 KB Output is correct
12 Correct 1026 ms 115464 KB Output is correct
13 Correct 1118 ms 121448 KB Output is correct
14 Correct 25 ms 5832 KB Output is correct
15 Correct 1006 ms 109332 KB Output is correct
16 Correct 924 ms 101352 KB Output is correct
17 Correct 1067 ms 102080 KB Output is correct
18 Correct 1035 ms 102104 KB Output is correct
19 Correct 1213 ms 109656 KB Output is correct
20 Correct 1309 ms 108304 KB Output is correct
21 Correct 918 ms 108992 KB Output is correct
22 Correct 897 ms 105260 KB Output is correct
23 Correct 951 ms 100712 KB Output is correct
24 Correct 954 ms 101168 KB Output is correct
25 Correct 1130 ms 112984 KB Output is correct
26 Correct 970 ms 100408 KB Output is correct
27 Correct 933 ms 100436 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6004 KB Output is correct
2 Correct 55 ms 8916 KB Output is correct
3 Correct 65 ms 9092 KB Output is correct
4 Correct 60 ms 9120 KB Output is correct
5 Correct 90 ms 9344 KB Output is correct
6 Correct 65 ms 9072 KB Output is correct
7 Correct 30 ms 5920 KB Output is correct
8 Correct 883 ms 105412 KB Output is correct
9 Correct 903 ms 105500 KB Output is correct
10 Correct 24 ms 5844 KB Output is correct
11 Correct 1040 ms 115432 KB Output is correct
12 Correct 1026 ms 115464 KB Output is correct
13 Correct 1118 ms 121448 KB Output is correct
14 Correct 25 ms 5832 KB Output is correct
15 Correct 1006 ms 109332 KB Output is correct
16 Correct 924 ms 101352 KB Output is correct
17 Correct 1067 ms 102080 KB Output is correct
18 Correct 1035 ms 102104 KB Output is correct
19 Correct 1213 ms 109656 KB Output is correct
20 Correct 1309 ms 108304 KB Output is correct
21 Correct 918 ms 108992 KB Output is correct
22 Correct 897 ms 105260 KB Output is correct
23 Correct 951 ms 100712 KB Output is correct
24 Correct 954 ms 101168 KB Output is correct
25 Correct 1130 ms 112984 KB Output is correct
26 Correct 970 ms 100408 KB Output is correct
27 Correct 933 ms 100436 KB Output is correct
28 Incorrect 26 ms 5708 KB Extra information in the output file
29 Halted 0 ms 0 KB -