oj.uz

Submission #710815

# Submission time Handle Problem Language Result Execution time Memory
710815 2023-03-15T20:57:55 Z sysia Inside information (BOI21_servers) C++17
50 / 100
 1008 ms 110408 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

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;

//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}};
    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;
			Cque.emplace_back(a, 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)) {
			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)) cout << "yes\n";
			else cout << "no\n";
			continue;
		} 
		if (l == a){
			//sciezka ma byc malejaca
			if (is_increasing(a, b, 0)) cout << "yes\n";
			else cout << "no\n";
			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]) cout << "yes\n";
		else cout << "no\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 23 ms 5452 KB Output is correct
2 Correct 52 ms 9648 KB Output is correct
3 Correct 80 ms 9652 KB Output is correct
4 Correct 54 ms 9752 KB Output is correct
5 Correct 75 ms 10052 KB Output is correct
6 Correct 64 ms 9588 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5452 KB Output is correct
2 Correct 52 ms 9648 KB Output is correct
3 Correct 80 ms 9652 KB Output is correct
4 Correct 54 ms 9752 KB Output is correct
5 Correct 75 ms 10052 KB Output is correct
6 Correct 64 ms 9588 KB Output is correct
7 Incorrect 24 ms 6376 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 34 ms 5472 KB Output is correct
2 Correct 795 ms 91056 KB Output is correct
3 Correct 816 ms 90968 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5472 KB Output is correct
2 Correct 795 ms 91056 KB Output is correct
3 Correct 816 ms 90968 KB Output is correct
4 Incorrect 24 ms 5456 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 5460 KB Output is correct
2 Correct 800 ms 110332 KB Output is correct
3 Correct 777 ms 110392 KB Output is correct
4 Correct 849 ms 109800 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5460 KB Output is correct
2 Correct 800 ms 110332 KB Output is correct
3 Correct 777 ms 110392 KB Output is correct
4 Correct 849 ms 109800 KB Output is correct
5 Incorrect 23 ms 6364 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 27 ms 5560 KB Output is correct
2 Correct 763 ms 95872 KB Output is correct
3 Correct 751 ms 96240 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5560 KB Output is correct
2 Correct 763 ms 95872 KB Output is correct
3 Correct 751 ms 96240 KB Output is correct
4 Incorrect 26 ms 6420 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 22 ms 5452 KB Output is correct
2 Correct 831 ms 110376 KB Output is correct
3 Correct 832 ms 110388 KB Output is correct
4 Correct 895 ms 109744 KB Output is correct
5 Correct 24 ms 6336 KB Output is correct
6 Correct 803 ms 95896 KB Output is correct
7 Correct 777 ms 96328 KB Output is correct
8 Correct 870 ms 97116 KB Output is correct
9 Correct 836 ms 96936 KB Output is correct
10 Correct 855 ms 103180 KB Output is correct
11 Correct 1008 ms 102064 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5452 KB Output is correct
2 Correct 831 ms 110376 KB Output is correct
3 Correct 832 ms 110388 KB Output is correct
4 Correct 895 ms 109744 KB Output is correct
5 Correct 24 ms 6336 KB Output is correct
6 Correct 803 ms 95896 KB Output is correct
7 Correct 777 ms 96328 KB Output is correct
8 Correct 870 ms 97116 KB Output is correct
9 Correct 836 ms 96936 KB Output is correct
10 Correct 855 ms 103180 KB Output is correct
11 Correct 1008 ms 102064 KB Output is correct
12 Incorrect 24 ms 6340 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 24 ms 5508 KB Output is correct
2 Correct 51 ms 9528 KB Output is correct
3 Correct 63 ms 9692 KB Output is correct
4 Correct 50 ms 9924 KB Output is correct
5 Correct 78 ms 10072 KB Output is correct
6 Correct 62 ms 9744 KB Output is correct
7 Correct 27 ms 6340 KB Output is correct
8 Correct 780 ms 93936 KB Output is correct
9 Correct 763 ms 93724 KB Output is correct
10 Correct 22 ms 6316 KB Output is correct
11 Correct 795 ms 110408 KB Output is correct
12 Correct 795 ms 110392 KB Output is correct
13 Correct 868 ms 109772 KB Output is correct
14 Correct 36 ms 6380 KB Output is correct
15 Correct 786 ms 95968 KB Output is correct
16 Correct 754 ms 96196 KB Output is correct
17 Correct 898 ms 97028 KB Output is correct
18 Correct 844 ms 96964 KB Output is correct
19 Correct 898 ms 103180 KB Output is correct
20 Correct 981 ms 102092 KB Output is correct
21 Correct 770 ms 94856 KB Output is correct
22 Correct 781 ms 94912 KB Output is correct
23 Correct 798 ms 95460 KB Output is correct
24 Correct 780 ms 95640 KB Output is correct
25 Correct 841 ms 99280 KB Output is correct
26 Correct 751 ms 95376 KB Output is correct
27 Correct 743 ms 95512 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5508 KB Output is correct
2 Correct 51 ms 9528 KB Output is correct
3 Correct 63 ms 9692 KB Output is correct
4 Correct 50 ms 9924 KB Output is correct
5 Correct 78 ms 10072 KB Output is correct
6 Correct 62 ms 9744 KB Output is correct
7 Correct 27 ms 6340 KB Output is correct
8 Correct 780 ms 93936 KB Output is correct
9 Correct 763 ms 93724 KB Output is correct
10 Correct 22 ms 6316 KB Output is correct
11 Correct 795 ms 110408 KB Output is correct
12 Correct 795 ms 110392 KB Output is correct
13 Correct 868 ms 109772 KB Output is correct
14 Correct 36 ms 6380 KB Output is correct
15 Correct 786 ms 95968 KB Output is correct
16 Correct 754 ms 96196 KB Output is correct
17 Correct 898 ms 97028 KB Output is correct
18 Correct 844 ms 96964 KB Output is correct
19 Correct 898 ms 103180 KB Output is correct
20 Correct 981 ms 102092 KB Output is correct
21 Correct 770 ms 94856 KB Output is correct
22 Correct 781 ms 94912 KB Output is correct
23 Correct 798 ms 95460 KB Output is correct
24 Correct 780 ms 95640 KB Output is correct
25 Correct 841 ms 99280 KB Output is correct
26 Correct 751 ms 95376 KB Output is correct
27 Correct 743 ms 95512 KB Output is correct
28 Incorrect 24 ms 6388 KB Extra information in the output file
29 Halted 0 ms 0 KB -