Submission #934181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934181	2024-02-26T23:14:02 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	50 / 100	318 ms	113648 KB

servers

#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;
}

Subtask #1
2.5 / 2.5

#	Verdict	Execution time	Memory	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

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	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	-

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	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

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	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	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	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

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	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	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	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	-

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	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

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	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	-

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	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

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	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	-

Submission #934181

Compilation message