oj.uz

Submission #677332

# Submission time Handle Problem Language Result Execution time Memory
677332 2023-01-02T21:13:43 Z YENGOYAN Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 53188 KB 
	/*
		//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
		\\                                    //
		//  271828___182845__904523__53602__  \\
		\\  87___47____13______52____66__24_  //
		//  97___75____72______47____09___36  \\
		\\  999595_____74______96____69___67  //
		//  62___77____24______07____66__30_  \\
		\\  35___35____47______59____45713__  //
		//                                    \\
		\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
												  */

	#include <iostream>
	#include <vector>
	#include <set>
	#include <map>
	#include <unordered_map>
	#include <unordered_map>
	#include <cmath>
	#include <climits>
	#include <algorithm>
	#include <random>
	#include <queue>
	#include <deque>
	#include <iomanip>
	#include <string>
	#include <tuple>
	#include <bitset>
	#include <chrono>
	#include <ctime>
	#include <fstream>
	#include <stack>
	#include <cstdio>

	using namespace std;
	using ll = long long;
	const int N = 1e5 + 5;
	const ll mod = 1e9 + 7, inf = 1e12;

	int n, k, timer = 0;
	vector<vector<pair<int, int>>> gp;
	vector<vector<int>> up;
	vector<int> achox, nvazox, d, tin, tout, par;

	void dfs(int u, int p, int h, int lst) {
		up[u][0] = p;
		par[u] = p;
		tin[u] = ++timer;
		for (int i = 1; i < 20; ++i) up[u][i] = up[up[u][i - 1]][i - 1];
		achox[u] = h;
		for (pair<int, int>& v : gp[u]) {
			if (v.first != p) {
				d[v.first] = d[u] + 1;
				if (v.second >= lst) dfs(v.first, u, h, v.second);
				else dfs(v.first, u, u, v.second);
			}
		}
		tout[u] = ++timer;
	}

	void dfs1(int u, int p, int h, int lst) {
		nvazox[u] = h;
		for (pair<int, int>& v : gp[u]) {
			if (v.first != p) {
				if (v.second <= lst) dfs1(v.first, u, h, v.second);
				else dfs1(v.first, u, u, v.second);
			}
		}
	}

	bool isAncestor(int u, int v) {
		return tin[u] > tin[v] && tout[u] < tout[v];
	}

	int lca(int u, int v) {
		if (isAncestor(u, v)) return v;
		if (isAncestor(v, u))return u;
		for (int i = 19; i >= 0; --i) {
			if (!isAncestor(v, up[u][i])) u = up[u][i];
		}
		return up[u][0];
	}

	void solve() {
		cin >> n >> k;
		vector<pair<pair<int, int>, int>> query;
		gp = vector<vector<pair<int, int>>>(n);
		vector<vector<int>> upd(n);
		up = vector<vector<int>>(n, vector<int>(20));
		nvazox = tin = tout = par = d = achox = vector<int>(n);
		vector<pair<pair<int, int>, int>> edg;
		map<pair<int, int>, int> mp;
		for (int i = 0; i < n + k - 1; ++i) {
			char c; cin >> c;
			if (c == 'S') {
				int u, v; cin >> u >> v;
				gp[--u].push_back({ --v, i + 1 });
				gp[v].push_back({ u, i + 1 });
				mp[{u, v}] = mp[{v, u}] = i + 1;
				//ws[{u, v }] = 1;
			}
			else {
				int a, d; cin >> a >> d;
				query.push_back({ {--a, --d}, i + 1 });
			}
		}
		dfs(0, 0, 0, 0);
		dfs1(0, 0, 0, 1e9);
		for (pair<pair<int, int>, int> x : query) {
			int A = x.first.first, D = x.first.second, w = x.second;
			int l = lca(A, D);
			int wa = 0, wd = 0;
			for (pair<int, int>& v : gp[l]) {
				if (v.first == par[l]) continue;
				if (tin[A] >= tin[v.first] && tout[A] <= tout[v.first]) wa = v.second;
				if (tin[D] >= tin[v.first] && tout[D] <= tout[v.first]) wd = v.second;
			}
			if (A == D) cout << "yes\n";
			else if (d[achox[A]] > d[l] || d[nvazox[D]] > d[l]) cout << "no\n";
			else if (tin[A] > tin[D] && tout[A] < tout[D]) {
				if (mp[{A, par[A]}] <= w) cout << "yes\n";
				else cout << "no\n";
			}
			else if (tin[A] < tin[D] && tout[A] > tout[D]) {
				bool f = 1;
				for (pair<int, int>& v : gp[A]) {
					if (v.first == par[A]) continue;
					if (tin[v.first] <= tin[D] && tout[v.first] >= tout[D] && v.second > w)  f = 0;
				}
				if (f) cout << "yes\n";
				else cout << "no\n";
			}
			else if (wa >= wd) {
				if (mp[{A, par[A]}] < w) cout << "yes\n";
				else cout << "no\n";
			}
			else cout << "no\n";
		}
		//while (1) {
		//	int A, D; cin >> A >> D;
		//	--A, --D;
		//	int l = lca(A, D);
		//	//continue;
		//	int wa = 0, wd = 0, w = 1e8;
		//	for (pair<int, int>& v : gp[l]) {
		//		if (v.first == par[l]) continue;
		//		if (tin[A] >= tin[v.first] && tout[A] <= tout[v.first]) wa = v.second;
		//		if (tin[D] >= tin[v.first] && tout[D] <= tout[v.first]) wd = v.second;
		//	}
		//	if (A == D) cout << "yes\n";
		//	else if (d[achox[A]] > d[l] || d[nvazox[D]] > d[l]) cout << "no1\n";
		//	else if (tin[A] > tin[D] && tout[A] < tout[D]) {
		//		if (mp[{A, par[A]}] <= w) cout << "yes\n";
		//		else cout << "no2\n";
		//	}
			/*
					9 0
	S 5 9
	S 4 6
	S 3 5
	S 1 2
	S 5 8
	S 5 7
	S 1 4
	S 3 1

	 1 3
			*/
		/*	else if (tin[A] < tin[D] && tout[A] > tout[D]) {
				bool f = 1;
				for (pair<int, int>& v : gp[A]) {
					if (v.first != par[A] && tin[v.first] <= tin[D] && tout[v.first] >= tout[D] && v.second > w)  f = 0;
				}
				if (f) cout << "yes\n";
				else cout << "no3\n";
			}
			else if (d[achox[A]] <= d[l] && d[nvazox[D]] <= d[l] && wa >= wd) {
				if (mp[{A, par[A]}] < w) cout << "yes\n";
				else cout << "no4\n";
			}
			else cout << "no5\n";
		}*/
	}

	/*
	TEST
	 6 9
	S 1 2
	S 1 3
	S 3 4
	Q 5 1
	S 4 5
	S 1 6
	Q  5 1
	Q 1 5
	Q 1 5
	Q 1 5
	Q 1 5
	Q 1 5
	Q 1 5
	Q 1 5

	*/

	int main() {
		ios_base::sync_with_stdio(0);
		cin.tie(NULL);
		//int _; cin >> _; while (_--)
			solve();
	}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2376 KB Output is correct
2 Correct 41 ms 4852 KB Output is correct
3 Correct 99 ms 5040 KB Output is correct
4 Correct 42 ms 4988 KB Output is correct
5 Correct 31 ms 5236 KB Output is correct
6 Correct 625 ms 4988 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2376 KB Output is correct
2 Correct 41 ms 4852 KB Output is correct
3 Correct 99 ms 5040 KB Output is correct
4 Correct 42 ms 4988 KB Output is correct
5 Correct 31 ms 5236 KB Output is correct
6 Correct 625 ms 4988 KB Output is correct
7 Runtime error 7 ms 3660 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2392 KB Output is correct
2 Execution timed out 3523 ms 45632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2392 KB Output is correct
2 Execution timed out 3523 ms 45632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2364 KB Output is correct
2 Correct 298 ms 53152 KB Output is correct
3 Correct 300 ms 53188 KB Output is correct
4 Correct 172 ms 52992 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2364 KB Output is correct
2 Correct 298 ms 53152 KB Output is correct
3 Correct 300 ms 53188 KB Output is correct
4 Correct 172 ms 52992 KB Output is correct
5 Runtime error 7 ms 3660 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2188 KB Output is correct
2 Correct 204 ms 47740 KB Output is correct
3 Correct 359 ms 48316 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2188 KB Output is correct
2 Correct 204 ms 47740 KB Output is correct
3 Correct 359 ms 48316 KB Output is correct
4 Runtime error 6 ms 3660 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2124 KB Output is correct
2 Correct 314 ms 52832 KB Output is correct
3 Correct 297 ms 52856 KB Output is correct
4 Correct 178 ms 53024 KB Output is correct
5 Correct 23 ms 2252 KB Output is correct
6 Correct 199 ms 47692 KB Output is correct
7 Correct 357 ms 48344 KB Output is correct
8 Correct 372 ms 48560 KB Output is correct
9 Correct 391 ms 48764 KB Output is correct
10 Correct 352 ms 53112 KB Output is correct
11 Correct 370 ms 52404 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2124 KB Output is correct
2 Correct 314 ms 52832 KB Output is correct
3 Correct 297 ms 52856 KB Output is correct
4 Correct 178 ms 53024 KB Output is correct
5 Correct 23 ms 2252 KB Output is correct
6 Correct 199 ms 47692 KB Output is correct
7 Correct 357 ms 48344 KB Output is correct
8 Correct 372 ms 48560 KB Output is correct
9 Correct 391 ms 48764 KB Output is correct
10 Correct 352 ms 53112 KB Output is correct
11 Correct 370 ms 52404 KB Output is correct
12 Runtime error 6 ms 3676 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2256 KB Output is correct
2 Correct 40 ms 4848 KB Output is correct
3 Correct 101 ms 4888 KB Output is correct
4 Correct 46 ms 4896 KB Output is correct
5 Correct 31 ms 5232 KB Output is correct
6 Correct 673 ms 5052 KB Output is correct
7 Correct 35 ms 3116 KB Output is correct
8 Execution timed out 3554 ms 47024 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2256 KB Output is correct
2 Correct 40 ms 4848 KB Output is correct
3 Correct 101 ms 4888 KB Output is correct
4 Correct 46 ms 4896 KB Output is correct
5 Correct 31 ms 5232 KB Output is correct
6 Correct 673 ms 5052 KB Output is correct
7 Correct 35 ms 3116 KB Output is correct
8 Execution timed out 3554 ms 47024 KB Time limit exceeded
9 Halted 0 ms 0 KB -