oj.uz

Submission #850735

# Submission time Handle Problem Language Result Execution time Memory
850735 2023-09-17T11:16:58 Z esomer Inside information (BOI21_servers) C++17
50 / 100
 337 ms 68032 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"
 
vector<int> depths;
 
void DFS(int x, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& parent){
	for(pair<int, int> p : adj[x]){
		int node = p.first;
		if(node == parent[x].first) continue;
		parent[node] = {x, p.second};
		depths[node] = depths[x] + 1;
		DFS(node, adj, parent);
	}
}
 
int kth(int a, int dist, vector<vector<int>>& binlift){
	for(int k = 0; k < 20; k++){
		if((1 << k) & dist){
			a = binlift[k][a];
		}
	}
	return a;
}
 
int lca(int a, int b, vector<vector<int>>& binlift){
	if(depths[a] < depths[b]){
		b = kth(b, depths[b] - depths[a], binlift);
	}else if(depths[b] < depths[a]){
		a = kth(a, depths[a] - depths[b], binlift);
	}
	if(a == b) return a;
	int anc = a;
	for(int k = 19; k >= 0; k--){
		if(binlift[k][a] == binlift[k][b]){
			anc = binlift[k][a];
		}else{
			a = binlift[k][a];
			b = binlift[k][b];
		}
	}
	return anc;
}
 
pair<int, int> increasing(int a, int anc, vector<vector<pair<int, int>>>& inc, vector<vector<int>>& binlift, vector<pair<int, int>>& parent){
	int dist = depths[a] - depths[anc];
	int good = 1;
	int lst = -1;
	// cout << "dist "<< dist << endl;
	for(int k = 0; k < 20; k++){
		if((1 << k) & dist){
			good = min(good, inc[k][a].first);
			lst = inc[k][a].second;
			// cout << "k "<< k << " inc/dec "<< inc[k][a].first << " a "<< a << " good "<< good <<  endl;
			// cout << "lst "<< lst << endl;
			a = binlift[k][a];
			if(a != anc && lst > parent[a].second) good = 0;
		}
	}
	return {good, lst};
}
 
pair<int, int> decreasing(int a, int anc, vector<vector<pair<int, int>>>& inc, vector<vector<int>>& binlift, vector<pair<int, int>>& parent){
	int dist = depths[a] - depths[anc];
	int good = 1;
	int lst = -1;
	// cout << "dist "<< dist << endl;
	for(int k = 0; k < 20; k++){
		if((1 << k) & dist){
			good = min(good, inc[k][a].first);
			lst = inc[k][a].second;
			// cout << "k "<< k << " inc/dec "<< inc[k][a].first << " a "<< a << " good "<< good <<  endl;
			// cout << "lst "<< lst << endl;
			a = binlift[k][a];
			if(a != anc && lst < parent[a].second) good = 0;
		}
	}
	return {good, lst};
}
 
void solve(){
	int N, K; cin >> N >> K;
	vector<vector<pair<int, int>>> adj(N);
	depths.resize(N);
	vector<tuple<int, int, int>> queries;
	for(int i = 0; i < N + K - 1; i++){
		char c; cin >> c;
		if(c == 'C'){
			cout << "NOT NOW" << endl;
			return;
		}else if(c == 'S'){
			int a, b; cin >> a >> b; a--; b--;
			adj[a].push_back({b, i});
			adj[b].push_back({a, i});
		}else{
			int a, d; cin >> a >> d; a--; d--;
			queries.push_back({a, d, i});
		}
	}
	vector<pair<int, int>> parent(N, {-1, -1});
	depths[0] = 0;
	DFS(0, adj, parent);
	vector<vector<int>> binlift(20, vector<int>(N));
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) binlift[k][i] = parent[i].first;
			else{
				if(binlift[k-1][i] == -1) binlift[k][i] = -1;
				else binlift[k][i] = binlift[k-1][binlift[k-1][i]];
			}
		}
	}
	vector<vector<pair<int, int>>> inc(20, vector<pair<int, int>>(N));
	vector<vector<pair<int, int>>> dec(20, vector<pair<int, int>>(N)); //From node to its ancestors.
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) inc[k][i] = {1, parent[i].second};
			else{
				if(binlift[k-1][i] == -1) inc[k][i] = inc[k-1][i];
				else{
					if(inc[k-1][i].first == 0 || inc[k-1][binlift[k-1][i]].first == 0 || (parent[binlift[k-1][i]].second != -1 && parent[binlift[k-1][i]].second < inc[k-1][i].second)){
						inc[k][i].first = 0;
					}else inc[k][i].first = 1;
					inc[k][i].second = inc[k-1][binlift[k-1][i]].second;
				}
			}
		}
	}
	for(int k = 0; k < 20; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) dec[k][i] = {1, parent[i].second};
			else{
				if(binlift[k-1][i] == -1) dec[k][i] = dec[k-1][i];
				else{
					if(dec[k-1][i].first == 0 || dec[k-1][binlift[k-1][i]].first == 0 || parent[binlift[k-1][i]].second > dec[k-1][i].second){
						dec[k][i].first = 0;
					}else dec[k][i].first = 1;
					dec[k][i].second = dec[k-1][binlift[k-1][i]].second;
				}
			}
		}
	}
	// for(int k = 0; k < 3; k++){
	// 	cout << "k "<< k << endl;
	// 	for(int i = 0; i < N; i++){
	// 		cout << "i "<< i << " dec "<< dec[k][i].first << " "<< dec[k][i].second << endl;
	// 		cout << "i "<< i << " binlift "<< binlift[k][i] << endl;
	// 	}
	// }
	// cout << "dec 3 2^1 "<< dec[1][3].first << endl;
	// cout << "PARENTS"<< endl;
	// for(int i = 0; i < N; i++){
	// 	cout << "i "<< i << endl;
	// 	cout << "parent "<< parent[i].first << " "<< parent[i].second << endl;
	// }
	vector<int> ans;
	for(tuple<int, int, int> t : queries){
		int a = get<0>(t);
		int d = get<1>(t);
		if(a == d){
			ans.push_back(1);
			continue;
		}
		// cout << "a "<< a << " d "<< d << " time "<< get<2>(t) << endl;
		int anc = lca(a, d, binlift);
		// cout << "anc "<< anc << endl;
		int mx = -1;
		if(anc != a) mx = parent[a].second;
		pair<int, int> firs = increasing(d, anc, inc, binlift, parent);
		pair<int, int> sec = decreasing(a, anc, dec, binlift, parent);
		mx = max(mx, max(firs.second, sec.second));
		// cout << "firs "<< firs.first << " "<< firs.second << " sec "<< sec.first << " " << sec.second << " mx "<< mx << endl;
		if(mx > get<2>(t) || firs.first == 0 || sec.first == 0 || (anc != a && anc != d && sec.second != -1 && firs.second > sec.second)){
			ans.push_back(0);
		}else ans.push_back(1);
 	}
	for(int x : ans) cout << (x == 1 ? "yes" : "no") << endl;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3016 KB Output is correct
2 Correct 60 ms 4968 KB Output is correct
3 Correct 42 ms 5060 KB Output is correct
4 Correct 60 ms 5072 KB Output is correct
5 Correct 41 ms 5120 KB Output is correct
6 Correct 44 ms 5092 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3016 KB Output is correct
2 Correct 60 ms 4968 KB Output is correct
3 Correct 42 ms 5060 KB Output is correct
4 Correct 60 ms 5072 KB Output is correct
5 Correct 41 ms 5120 KB Output is correct
6 Correct 44 ms 5092 KB Output is correct
7 Incorrect 1 ms 344 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 28 ms 3016 KB Output is correct
2 Correct 161 ms 59596 KB Output is correct
3 Correct 153 ms 59592 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3016 KB Output is correct
2 Correct 161 ms 59596 KB Output is correct
3 Correct 153 ms 59592 KB Output is correct
4 Incorrect 1 ms 344 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 3016 KB Output is correct
2 Correct 107 ms 67924 KB Output is correct
3 Correct 108 ms 67928 KB Output is correct
4 Correct 139 ms 67924 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3016 KB Output is correct
2 Correct 107 ms 67924 KB Output is correct
3 Correct 108 ms 67928 KB Output is correct
4 Correct 139 ms 67924 KB Output is correct
5 Incorrect 1 ms 344 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 28 ms 3016 KB Output is correct
2 Correct 156 ms 59480 KB Output is correct
3 Correct 144 ms 60272 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3016 KB Output is correct
2 Correct 156 ms 59480 KB Output is correct
3 Correct 144 ms 60272 KB Output is correct
4 Incorrect 1 ms 344 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 26 ms 3024 KB Output is correct
2 Correct 113 ms 67928 KB Output is correct
3 Correct 118 ms 68024 KB Output is correct
4 Correct 136 ms 67928 KB Output is correct
5 Correct 29 ms 3016 KB Output is correct
6 Correct 168 ms 59600 KB Output is correct
7 Correct 124 ms 59992 KB Output is correct
8 Correct 224 ms 60376 KB Output is correct
9 Correct 174 ms 60504 KB Output is correct
10 Correct 148 ms 64856 KB Output is correct
11 Correct 213 ms 64052 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3024 KB Output is correct
2 Correct 113 ms 67928 KB Output is correct
3 Correct 118 ms 68024 KB Output is correct
4 Correct 136 ms 67928 KB Output is correct
5 Correct 29 ms 3016 KB Output is correct
6 Correct 168 ms 59600 KB Output is correct
7 Correct 124 ms 59992 KB Output is correct
8 Correct 224 ms 60376 KB Output is correct
9 Correct 174 ms 60504 KB Output is correct
10 Correct 148 ms 64856 KB Output is correct
11 Correct 213 ms 64052 KB Output is correct
12 Incorrect 1 ms 344 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 29 ms 3016 KB Output is correct
2 Correct 54 ms 4932 KB Output is correct
3 Correct 44 ms 4988 KB Output is correct
4 Correct 61 ms 5072 KB Output is correct
5 Correct 41 ms 5124 KB Output is correct
6 Correct 46 ms 5092 KB Output is correct
7 Correct 28 ms 3280 KB Output is correct
8 Correct 159 ms 59596 KB Output is correct
9 Correct 143 ms 59612 KB Output is correct
10 Correct 24 ms 3016 KB Output is correct
11 Correct 110 ms 67928 KB Output is correct
12 Correct 108 ms 68032 KB Output is correct
13 Correct 132 ms 67928 KB Output is correct
14 Correct 29 ms 3016 KB Output is correct
15 Correct 184 ms 59480 KB Output is correct
16 Correct 152 ms 59940 KB Output is correct
17 Correct 294 ms 60248 KB Output is correct
18 Correct 181 ms 62640 KB Output is correct
19 Correct 202 ms 66856 KB Output is correct
20 Correct 337 ms 66448 KB Output is correct
21 Correct 294 ms 61600 KB Output is correct
22 Correct 233 ms 61676 KB Output is correct
23 Correct 221 ms 62128 KB Output is correct
24 Correct 293 ms 62252 KB Output is correct
25 Correct 225 ms 63964 KB Output is correct
26 Correct 126 ms 61592 KB Output is correct
27 Correct 114 ms 61468 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3016 KB Output is correct
2 Correct 54 ms 4932 KB Output is correct
3 Correct 44 ms 4988 KB Output is correct
4 Correct 61 ms 5072 KB Output is correct
5 Correct 41 ms 5124 KB Output is correct
6 Correct 46 ms 5092 KB Output is correct
7 Correct 28 ms 3280 KB Output is correct
8 Correct 159 ms 59596 KB Output is correct
9 Correct 143 ms 59612 KB Output is correct
10 Correct 24 ms 3016 KB Output is correct
11 Correct 110 ms 67928 KB Output is correct
12 Correct 108 ms 68032 KB Output is correct
13 Correct 132 ms 67928 KB Output is correct
14 Correct 29 ms 3016 KB Output is correct
15 Correct 184 ms 59480 KB Output is correct
16 Correct 152 ms 59940 KB Output is correct
17 Correct 294 ms 60248 KB Output is correct
18 Correct 181 ms 62640 KB Output is correct
19 Correct 202 ms 66856 KB Output is correct
20 Correct 337 ms 66448 KB Output is correct
21 Correct 294 ms 61600 KB Output is correct
22 Correct 233 ms 61676 KB Output is correct
23 Correct 221 ms 62128 KB Output is correct
24 Correct 293 ms 62252 KB Output is correct
25 Correct 225 ms 63964 KB Output is correct
26 Correct 126 ms 61592 KB Output is correct
27 Correct 114 ms 61468 KB Output is correct
28 Incorrect 1 ms 644 KB Extra information in the output file
29 Halted 0 ms 0 KB -