oj.uz

Submission #677335

# Submission time Handle Problem Language Result Execution time Memory
677335 2023-01-02T21:21:50 Z YENGOYAN Inside information (BOI21_servers) C++17
50 / 100
 280 ms 41720 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, qash;

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;
			qash[v.first] = v.second;
			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));
	qash = 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;
		}
		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;
		int u = A;
		for (int i = 19; i >= 0; --i) {
			if (d[up[u][i]] > d[l]) u = up[u][i];
		}
		if (d[u] > d[l]) wa = qash[u];
		u = D;
		for (int i = 19; i >= 0; --i) {
			if (d[up[u][i]] > d[l]) u = up[u][i];
		}
		if (d[u] > d[l]) wd = qash[u];
		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 (qash[A] <= w) cout << "yes\n";
			else cout << "no\n";
		}
		else if (tin[A] < tin[D] && tout[A] > tout[D]) {
			bool f = 1;
			if (wd > w) f = 0;
			if (f) cout << "yes\n";
			else cout << "no\n";
		}
		else if (wa >= wd) {
			if (qash[A] < w) cout << "yes\n";
			else cout << "no\n";
		}
		else cout << "no\n";
	}
}

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 29 ms 2204 KB Output is correct
2 Correct 42 ms 2888 KB Output is correct
3 Correct 37 ms 3048 KB Output is correct
4 Correct 72 ms 3012 KB Output is correct
5 Correct 52 ms 3360 KB Output is correct
6 Correct 37 ms 3060 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2204 KB Output is correct
2 Correct 42 ms 2888 KB Output is correct
3 Correct 37 ms 3048 KB Output is correct
4 Correct 72 ms 3012 KB Output is correct
5 Correct 52 ms 3360 KB Output is correct
6 Correct 37 ms 3060 KB Output is correct
7 Runtime error 6 ms 3532 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2144 KB Output is correct
2 Correct 186 ms 29908 KB Output is correct
3 Correct 168 ms 32896 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2144 KB Output is correct
2 Correct 186 ms 29908 KB Output is correct
3 Correct 168 ms 32896 KB Output is correct
4 Runtime error 6 ms 3660 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2120 KB Output is correct
2 Correct 171 ms 38252 KB Output is correct
3 Correct 161 ms 38348 KB Output is correct
4 Correct 168 ms 38292 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2120 KB Output is correct
2 Correct 171 ms 38252 KB Output is correct
3 Correct 161 ms 38348 KB Output is correct
4 Correct 168 ms 38292 KB Output is correct
5 Runtime error 6 ms 3536 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 28 ms 2152 KB Output is correct
2 Correct 130 ms 29872 KB Output is correct
3 Correct 156 ms 30320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2152 KB Output is correct
2 Correct 130 ms 29872 KB Output is correct
3 Correct 156 ms 30320 KB Output is correct
4 Runtime error 7 ms 3532 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 30 ms 2148 KB Output is correct
2 Correct 147 ms 38264 KB Output is correct
3 Correct 158 ms 38312 KB Output is correct
4 Correct 174 ms 38432 KB Output is correct
5 Correct 28 ms 2116 KB Output is correct
6 Correct 178 ms 29788 KB Output is correct
7 Correct 156 ms 30368 KB Output is correct
8 Correct 208 ms 30680 KB Output is correct
9 Correct 174 ms 30720 KB Output is correct
10 Correct 230 ms 35244 KB Output is correct
11 Correct 273 ms 34432 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2148 KB Output is correct
2 Correct 147 ms 38264 KB Output is correct
3 Correct 158 ms 38312 KB Output is correct
4 Correct 174 ms 38432 KB Output is correct
5 Correct 28 ms 2116 KB Output is correct
6 Correct 178 ms 29788 KB Output is correct
7 Correct 156 ms 30368 KB Output is correct
8 Correct 208 ms 30680 KB Output is correct
9 Correct 174 ms 30720 KB Output is correct
10 Correct 230 ms 35244 KB Output is correct
11 Correct 273 ms 34432 KB Output is correct
12 Runtime error 7 ms 3524 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2116 KB Output is correct
2 Correct 51 ms 3048 KB Output is correct
3 Correct 36 ms 3156 KB Output is correct
4 Correct 59 ms 3088 KB Output is correct
5 Correct 46 ms 3340 KB Output is correct
6 Correct 44 ms 2976 KB Output is correct
7 Correct 27 ms 2252 KB Output is correct
8 Correct 159 ms 29948 KB Output is correct
9 Correct 164 ms 32740 KB Output is correct
10 Correct 28 ms 3088 KB Output is correct
11 Correct 166 ms 41652 KB Output is correct
12 Correct 157 ms 41720 KB Output is correct
13 Correct 169 ms 41584 KB Output is correct
14 Correct 29 ms 3012 KB Output is correct
15 Correct 142 ms 33164 KB Output is correct
16 Correct 159 ms 33568 KB Output is correct
17 Correct 226 ms 34040 KB Output is correct
18 Correct 183 ms 34044 KB Output is correct
19 Correct 249 ms 38528 KB Output is correct
20 Correct 280 ms 37804 KB Output is correct
21 Correct 169 ms 33272 KB Output is correct
22 Correct 167 ms 33292 KB Output is correct
23 Correct 167 ms 33536 KB Output is correct
24 Correct 169 ms 33588 KB Output is correct
25 Correct 201 ms 35424 KB Output is correct
26 Correct 169 ms 33112 KB Output is correct
27 Correct 150 ms 33184 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2116 KB Output is correct
2 Correct 51 ms 3048 KB Output is correct
3 Correct 36 ms 3156 KB Output is correct
4 Correct 59 ms 3088 KB Output is correct
5 Correct 46 ms 3340 KB Output is correct
6 Correct 44 ms 2976 KB Output is correct
7 Correct 27 ms 2252 KB Output is correct
8 Correct 159 ms 29948 KB Output is correct
9 Correct 164 ms 32740 KB Output is correct
10 Correct 28 ms 3088 KB Output is correct
11 Correct 166 ms 41652 KB Output is correct
12 Correct 157 ms 41720 KB Output is correct
13 Correct 169 ms 41584 KB Output is correct
14 Correct 29 ms 3012 KB Output is correct
15 Correct 142 ms 33164 KB Output is correct
16 Correct 159 ms 33568 KB Output is correct
17 Correct 226 ms 34040 KB Output is correct
18 Correct 183 ms 34044 KB Output is correct
19 Correct 249 ms 38528 KB Output is correct
20 Correct 280 ms 37804 KB Output is correct
21 Correct 169 ms 33272 KB Output is correct
22 Correct 167 ms 33292 KB Output is correct
23 Correct 167 ms 33536 KB Output is correct
24 Correct 169 ms 33588 KB Output is correct
25 Correct 201 ms 35424 KB Output is correct
26 Correct 169 ms 33112 KB Output is correct
27 Correct 150 ms 33184 KB Output is correct
28 Runtime error 7 ms 3660 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -