답안 #934159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934159 2024-02-26T22:05:26 Z Joshua_Andersson Inside information (BOI21_servers) C++14
15 / 100
3500 ms 75028 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

const int maxn = int(1.5e5);
int tin[maxn];
int tout[maxn];
int timer = 0;
int up[18][maxn];
int upmax[18][maxn];
int upv[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	tin[u] = timer++;
	up[0][u] = p;
	upmax[0][u] = upv[u];

	repp(d,1,18)
	{
		up[d][u] = up[d - 1][up[d - 1][u]];
		upmax[d][u] = max(upmax[d - 1][u], upmax[d - 1][up[d - 1][u]]);
	}
	

	repe(e, edges[u]) if (e.first != p) upv[e.first] = e.second, dfs(e.first, u, p1, _p2, edges);

	tout[u] = timer++;
}

bool isancestor(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int pathmax(int a, int b)
{
	if (isancestor(a, b)) return -1;
	int ret = -1;
	for (int d = 17; d >= 0; d--)
	{
		if (!isancestor(up[d][a], b))
		{
			ret = max(ret, upmax[d][a]);
			a = up[d][a];
		}
	}
	return max(ret, upmax[0][a]);
}

signed main()
{
	fast();

	int n, q;
	cin >> n >> q;

	vvi queries;
	int t = 0;
	vector<vector<p2>> edges(n);
	rep(i, n + q - 1)
	{
		char c;
		cin >> c;
		if (c=='S')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			edges[a].emplace_back(b, t);
			edges[b].emplace_back(a, t);
			t++;
		}
		else if (c=='Q')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			queries.push_back({ 0, b, a, t-1 });
		}
		else
		{
			int c;
			cin >> c;
			c--;
			queries.push_back({ 1, c, -1, t-1 });
		}
	}
	dfs(0, 0, -1, -1, edges);

	auto getmax = [&](int a, int b)
	{
		return max(pathmax(a, b), pathmax(b, a));
	};

	auto pathgood = [&](int a, int b, int t)
	{
		if (getmax(a, b) > t) return false;
		// all edges <= t
		// from b->lca increasing
		// from a->lca decreasing
		bool good = 1;
		int u = b;
		int prev = inf;
		while (!isancestor(u, a))
		{
			good &= upv[u] < prev;
			prev = upv[u];
			u = up[0][u];
		}
		
		u = a;
		int v = -1;
		while (!isancestor(u, b))
		{
			good &= upv[u] > v;
			v = upv[u];
			u = up[0][u];
		}

		return good&&(v<prev);
	};

	repe(q, queries)
	{
		int type=q[0], a=q[1], b=q[2], t=q[3];
		
		if (type==0)
		{
			cout << (pathgood(a, b, t) ? "yes" : "no") << "\n";
		}
		
	}

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 52996 KB Output is correct
2 Correct 46 ms 53552 KB Output is correct
3 Correct 43 ms 54012 KB Output is correct
4 Correct 57 ms 53880 KB Output is correct
5 Correct 361 ms 54268 KB Output is correct
6 Correct 41 ms 53688 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 52996 KB Output is correct
2 Correct 46 ms 53552 KB Output is correct
3 Correct 43 ms 54012 KB Output is correct
4 Correct 57 ms 53880 KB Output is correct
5 Correct 361 ms 54268 KB Output is correct
6 Correct 41 ms 53688 KB Output is correct
7 Incorrect 34 ms 52996 KB Extra information in the output file
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 52988 KB Output is correct
2 Correct 159 ms 64520 KB Output is correct
3 Correct 188 ms 64576 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 52988 KB Output is correct
2 Correct 159 ms 64520 KB Output is correct
3 Correct 188 ms 64576 KB Output is correct
4 Incorrect 33 ms 52992 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 52988 KB Output is correct
2 Correct 151 ms 75028 KB Output is correct
3 Correct 201 ms 74756 KB Output is correct
4 Execution timed out 3530 ms 74216 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 52988 KB Output is correct
2 Correct 151 ms 75028 KB Output is correct
3 Correct 201 ms 74756 KB Output is correct
4 Execution timed out 3530 ms 74216 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 52992 KB Output is correct
2 Correct 126 ms 65532 KB Output is correct
3 Correct 167 ms 65672 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 52992 KB Output is correct
2 Correct 126 ms 65532 KB Output is correct
3 Correct 167 ms 65672 KB Output is correct
4 Incorrect 32 ms 52892 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 52988 KB Output is correct
2 Correct 197 ms 74836 KB Output is correct
3 Correct 207 ms 74748 KB Output is correct
4 Execution timed out 3567 ms 74168 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 52988 KB Output is correct
2 Correct 197 ms 74836 KB Output is correct
3 Correct 207 ms 74748 KB Output is correct
4 Execution timed out 3567 ms 74168 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 53156 KB Output is correct
2 Correct 45 ms 53716 KB Output is correct
3 Correct 53 ms 53756 KB Output is correct
4 Correct 57 ms 54012 KB Output is correct
5 Correct 341 ms 53996 KB Output is correct
6 Correct 53 ms 53788 KB Output is correct
7 Correct 43 ms 52988 KB Output is correct
8 Correct 150 ms 64560 KB Output is correct
9 Correct 158 ms 64628 KB Output is correct
10 Correct 37 ms 52944 KB Output is correct
11 Correct 205 ms 74872 KB Output is correct
12 Correct 162 ms 74656 KB Output is correct
13 Execution timed out 3518 ms 74188 KB Time limit exceeded
14 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 53156 KB Output is correct
2 Correct 45 ms 53716 KB Output is correct
3 Correct 53 ms 53756 KB Output is correct
4 Correct 57 ms 54012 KB Output is correct
5 Correct 341 ms 53996 KB Output is correct
6 Correct 53 ms 53788 KB Output is correct
7 Correct 43 ms 52988 KB Output is correct
8 Correct 150 ms 64560 KB Output is correct
9 Correct 158 ms 64628 KB Output is correct
10 Correct 37 ms 52944 KB Output is correct
11 Correct 205 ms 74872 KB Output is correct
12 Correct 162 ms 74656 KB Output is correct
13 Execution timed out 3518 ms 74188 KB Time limit exceeded
14 Halted 0 ms 0 KB -