oj.uz

답안 #677333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677333 2023-01-02T21:18:11 Z YENGOYAN Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 38368 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;
		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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2136 KB Output is correct
2 Correct 41 ms 2924 KB Output is correct
3 Correct 100 ms 3144 KB Output is correct
4 Correct 41 ms 3156 KB Output is correct
5 Correct 32 ms 3364 KB Output is correct
6 Correct 722 ms 3116 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2136 KB Output is correct
2 Correct 41 ms 2924 KB Output is correct
3 Correct 100 ms 3144 KB Output is correct
4 Correct 41 ms 3156 KB Output is correct
5 Correct 32 ms 3364 KB Output is correct
6 Correct 722 ms 3116 KB Output is correct
7 Runtime error 6 ms 3532 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 2224 KB Output is correct
2 Execution timed out 3551 ms 29520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 2224 KB Output is correct
2 Execution timed out 3551 ms 29520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2252 KB Output is correct
2 Correct 146 ms 38368 KB Output is correct
3 Correct 149 ms 38304 KB Output is correct
4 Correct 103 ms 38320 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2252 KB Output is correct
2 Correct 146 ms 38368 KB Output is correct
3 Correct 149 ms 38304 KB Output is correct
4 Correct 103 ms 38320 KB Output is correct
5 Runtime error 10 ms 3636 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2216 KB Output is correct
2 Correct 118 ms 29856 KB Output is correct
3 Correct 156 ms 30332 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2216 KB Output is correct
2 Correct 118 ms 29856 KB Output is correct
3 Correct 156 ms 30332 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2192 KB Output is correct
2 Correct 166 ms 38296 KB Output is correct
3 Correct 152 ms 38360 KB Output is correct
4 Correct 94 ms 38244 KB Output is correct
5 Correct 24 ms 2188 KB Output is correct
6 Correct 143 ms 29888 KB Output is correct
7 Correct 145 ms 30360 KB Output is correct
8 Correct 180 ms 30720 KB Output is correct
9 Correct 181 ms 30728 KB Output is correct
10 Correct 197 ms 35144 KB Output is correct
11 Correct 238 ms 34432 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2192 KB Output is correct
2 Correct 166 ms 38296 KB Output is correct
3 Correct 152 ms 38360 KB Output is correct
4 Correct 94 ms 38244 KB Output is correct
5 Correct 24 ms 2188 KB Output is correct
6 Correct 143 ms 29888 KB Output is correct
7 Correct 145 ms 30360 KB Output is correct
8 Correct 180 ms 30720 KB Output is correct
9 Correct 181 ms 30728 KB Output is correct
10 Correct 197 ms 35144 KB Output is correct
11 Correct 238 ms 34432 KB Output is correct
12 Runtime error 6 ms 3624 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2120 KB Output is correct
2 Correct 38 ms 2908 KB Output is correct
3 Correct 103 ms 3132 KB Output is correct
4 Correct 49 ms 3088 KB Output is correct
5 Correct 28 ms 3336 KB Output is correct
6 Correct 721 ms 3068 KB Output is correct
7 Correct 35 ms 2244 KB Output is correct
8 Execution timed out 3564 ms 29520 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2120 KB Output is correct
2 Correct 38 ms 2908 KB Output is correct
3 Correct 103 ms 3132 KB Output is correct
4 Correct 49 ms 3088 KB Output is correct
5 Correct 28 ms 3336 KB Output is correct
6 Correct 721 ms 3068 KB Output is correct
7 Correct 35 ms 2244 KB Output is correct
8 Execution timed out 3564 ms 29520 KB Time limit exceeded
9 Halted 0 ms 0 KB -