Submission #850735

#	Time	Username	Problem	Language	Result	Execution time	Memory
850735		esomer	Inside information (BOI21_servers)	C++17	50 / 100	337 ms	68032 KiB

servers

#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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5