답안 #934181

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934181 2024-02-26T23:14:02 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
318 ms 113648 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[maxn][18];
int upincreasing[maxn][18];
int updecreasing[maxn][18];
int upmax[maxn][18];
int upv[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	tin[u] = timer++;
	up[u][0] = p;
	upmax[u][0] = upv[u];
	upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p==0 || u==0;
	updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p==0 || u==0;
	repp(d,1,18)
	{
		int mid = up[u][d - 1];
		up[u][d] = up[mid][d - 1];
		upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
		upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
		updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
	}
	

	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[a][d], b))
		{
			ret = max(ret, upmax[a][d]);
			a = up[a][d];
		}
	}
	return max(ret, upmax[a][0]);
}

signed main()
{
	fast();

	//ifstream in("C:\\Users\\Matis\\desktop\\comp_prog\\x64\\debug\\in.txt");
	//cin.rdbuf(in.rdbuf());

	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;
		for (int d = 17; d >= 0; d--)
		{
			if (!isancestor(up[u][d],a))
			{
				good &= updecreasing[u][d];
				u = up[u][d];
			}
		}
		if (!isancestor(u,a))
		{
			prev = upmax[u][0];
		}
		

		u = a;
		int v = -1;
		for (int d = 17; d >= 0; d--)
		{
			if (!isancestor(up[u][d], b))
			{
				good &= upincreasing[u][d];
				u = up[u][d];
			}
		}
		if (!isancestor(u, b))
		{
			v = upmax[u][0];
		}

		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";
		}
		else
		{

		}
	}

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 18176 KB Output is correct
2 Correct 46 ms 20948 KB Output is correct
3 Correct 45 ms 20892 KB Output is correct
4 Correct 51 ms 20996 KB Output is correct
5 Correct 62 ms 21348 KB Output is correct
6 Correct 49 ms 20992 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 18176 KB Output is correct
2 Correct 46 ms 20948 KB Output is correct
3 Correct 45 ms 20892 KB Output is correct
4 Correct 51 ms 20996 KB Output is correct
5 Correct 62 ms 21348 KB Output is correct
6 Correct 49 ms 20992 KB Output is correct
7 Incorrect 37 ms 17924 KB Extra information in the output file
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 17928 KB Output is correct
2 Correct 156 ms 97396 KB Output is correct
3 Correct 180 ms 97592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 17928 KB Output is correct
2 Correct 156 ms 97396 KB Output is correct
3 Correct 180 ms 97592 KB Output is correct
4 Incorrect 30 ms 17928 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18152 KB Output is correct
2 Correct 193 ms 113512 KB Output is correct
3 Correct 201 ms 113380 KB Output is correct
4 Correct 240 ms 112832 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18152 KB Output is correct
2 Correct 193 ms 113512 KB Output is correct
3 Correct 201 ms 113380 KB Output is correct
4 Correct 240 ms 112832 KB Output is correct
5 Incorrect 29 ms 18188 KB Extra information in the output file
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 18152 KB Output is correct
2 Correct 171 ms 98576 KB Output is correct
3 Correct 169 ms 98560 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 18152 KB Output is correct
2 Correct 171 ms 98576 KB Output is correct
3 Correct 169 ms 98560 KB Output is correct
4 Incorrect 34 ms 17920 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 17920 KB Output is correct
2 Correct 171 ms 113432 KB Output is correct
3 Correct 204 ms 113648 KB Output is correct
4 Correct 223 ms 112704 KB Output is correct
5 Correct 32 ms 18200 KB Output is correct
6 Correct 188 ms 98416 KB Output is correct
7 Correct 162 ms 98324 KB Output is correct
8 Correct 231 ms 99332 KB Output is correct
9 Correct 213 ms 99432 KB Output is correct
10 Correct 233 ms 105984 KB Output is correct
11 Correct 263 ms 104980 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 17920 KB Output is correct
2 Correct 171 ms 113432 KB Output is correct
3 Correct 204 ms 113648 KB Output is correct
4 Correct 223 ms 112704 KB Output is correct
5 Correct 32 ms 18200 KB Output is correct
6 Correct 188 ms 98416 KB Output is correct
7 Correct 162 ms 98324 KB Output is correct
8 Correct 231 ms 99332 KB Output is correct
9 Correct 213 ms 99432 KB Output is correct
10 Correct 233 ms 105984 KB Output is correct
11 Correct 263 ms 104980 KB Output is correct
12 Incorrect 27 ms 18188 KB Extra information in the output file
13 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 18100 KB Output is correct
2 Correct 44 ms 20992 KB Output is correct
3 Correct 41 ms 21048 KB Output is correct
4 Correct 51 ms 21004 KB Output is correct
5 Correct 60 ms 21500 KB Output is correct
6 Correct 41 ms 20924 KB Output is correct
7 Correct 32 ms 17924 KB Output is correct
8 Correct 166 ms 97340 KB Output is correct
9 Correct 164 ms 97392 KB Output is correct
10 Correct 28 ms 18068 KB Output is correct
11 Correct 181 ms 113472 KB Output is correct
12 Correct 163 ms 113548 KB Output is correct
13 Correct 222 ms 112792 KB Output is correct
14 Correct 32 ms 18140 KB Output is correct
15 Correct 171 ms 98356 KB Output is correct
16 Correct 156 ms 98828 KB Output is correct
17 Correct 220 ms 99328 KB Output is correct
18 Correct 208 ms 99228 KB Output is correct
19 Correct 202 ms 105960 KB Output is correct
20 Correct 318 ms 104844 KB Output is correct
21 Correct 176 ms 97636 KB Output is correct
22 Correct 162 ms 97792 KB Output is correct
23 Correct 171 ms 98304 KB Output is correct
24 Correct 173 ms 98308 KB Output is correct
25 Correct 228 ms 102040 KB Output is correct
26 Correct 167 ms 98356 KB Output is correct
27 Correct 136 ms 98300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 18100 KB Output is correct
2 Correct 44 ms 20992 KB Output is correct
3 Correct 41 ms 21048 KB Output is correct
4 Correct 51 ms 21004 KB Output is correct
5 Correct 60 ms 21500 KB Output is correct
6 Correct 41 ms 20924 KB Output is correct
7 Correct 32 ms 17924 KB Output is correct
8 Correct 166 ms 97340 KB Output is correct
9 Correct 164 ms 97392 KB Output is correct
10 Correct 28 ms 18068 KB Output is correct
11 Correct 181 ms 113472 KB Output is correct
12 Correct 163 ms 113548 KB Output is correct
13 Correct 222 ms 112792 KB Output is correct
14 Correct 32 ms 18140 KB Output is correct
15 Correct 171 ms 98356 KB Output is correct
16 Correct 156 ms 98828 KB Output is correct
17 Correct 220 ms 99328 KB Output is correct
18 Correct 208 ms 99228 KB Output is correct
19 Correct 202 ms 105960 KB Output is correct
20 Correct 318 ms 104844 KB Output is correct
21 Correct 176 ms 97636 KB Output is correct
22 Correct 162 ms 97792 KB Output is correct
23 Correct 171 ms 98304 KB Output is correct
24 Correct 173 ms 98308 KB Output is correct
25 Correct 228 ms 102040 KB Output is correct
26 Correct 167 ms 98356 KB Output is correct
27 Correct 136 ms 98300 KB Output is correct
28 Incorrect 32 ms 18176 KB Extra information in the output file
29 Halted 0 ms 0 KB -