Submission #934182

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934182	2024-02-26T23:15:05 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	50 / 100	251 ms	58860 KB

servers

#include <bits/stdc++.h>
using namespace std;

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

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];
bool upincreasing[maxn][18];
bool 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	15628 KB	Output is correct
2	Correct	44 ms	18428 KB	Output is correct
3	Correct	41 ms	17916 KB	Output is correct
4	Correct	49 ms	17924 KB	Output is correct
5	Correct	62 ms	18424 KB	Output is correct
6	Correct	40 ms	17916 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	15628 KB	Output is correct
2	Correct	44 ms	18428 KB	Output is correct
3	Correct	41 ms	17916 KB	Output is correct
4	Correct	49 ms	17924 KB	Output is correct
5	Correct	62 ms	18424 KB	Output is correct
6	Correct	40 ms	17916 KB	Output is correct
7	Incorrect	38 ms	15588 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	32 ms	15616 KB	Output is correct
2	Correct	120 ms	42764 KB	Output is correct
3	Correct	126 ms	42612 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	15616 KB	Output is correct
2	Correct	120 ms	42764 KB	Output is correct
3	Correct	126 ms	42612 KB	Output is correct
4	Incorrect	38 ms	15624 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	29 ms	15628 KB	Output is correct
2	Correct	151 ms	58628 KB	Output is correct
3	Correct	141 ms	58732 KB	Output is correct
4	Correct	153 ms	58528 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	15628 KB	Output is correct
2	Correct	151 ms	58628 KB	Output is correct
3	Correct	141 ms	58732 KB	Output is correct
4	Correct	153 ms	58528 KB	Output is correct
5	Incorrect	28 ms	15504 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	42 ms	15516 KB	Output is correct
2	Correct	155 ms	42840 KB	Output is correct
3	Correct	138 ms	42720 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	15516 KB	Output is correct
2	Correct	155 ms	42840 KB	Output is correct
3	Correct	138 ms	42720 KB	Output is correct
4	Incorrect	34 ms	15624 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	30 ms	15584 KB	Output is correct
2	Correct	156 ms	58628 KB	Output is correct
3	Correct	148 ms	58860 KB	Output is correct
4	Correct	176 ms	58712 KB	Output is correct
5	Correct	35 ms	15484 KB	Output is correct
6	Correct	140 ms	42664 KB	Output is correct
7	Correct	159 ms	42748 KB	Output is correct
8	Correct	178 ms	43436 KB	Output is correct
9	Correct	156 ms	43440 KB	Output is correct
10	Correct	248 ms	48896 KB	Output is correct
11	Correct	251 ms	47964 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	15584 KB	Output is correct
2	Correct	156 ms	58628 KB	Output is correct
3	Correct	148 ms	58860 KB	Output is correct
4	Correct	176 ms	58712 KB	Output is correct
5	Correct	35 ms	15484 KB	Output is correct
6	Correct	140 ms	42664 KB	Output is correct
7	Correct	159 ms	42748 KB	Output is correct
8	Correct	178 ms	43436 KB	Output is correct
9	Correct	156 ms	43440 KB	Output is correct
10	Correct	248 ms	48896 KB	Output is correct
11	Correct	251 ms	47964 KB	Output is correct
12	Incorrect	31 ms	15372 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	36 ms	15612 KB	Output is correct
2	Correct	41 ms	17896 KB	Output is correct
3	Correct	43 ms	17932 KB	Output is correct
4	Correct	61 ms	18136 KB	Output is correct
5	Correct	58 ms	18476 KB	Output is correct
6	Correct	41 ms	17780 KB	Output is correct
7	Correct	32 ms	15628 KB	Output is correct
8	Correct	130 ms	42612 KB	Output is correct
9	Correct	158 ms	42608 KB	Output is correct
10	Correct	29 ms	15612 KB	Output is correct
11	Correct	143 ms	58592 KB	Output is correct
12	Correct	168 ms	58620 KB	Output is correct
13	Correct	148 ms	58676 KB	Output is correct
14	Correct	33 ms	15620 KB	Output is correct
15	Correct	121 ms	42756 KB	Output is correct
16	Correct	154 ms	42676 KB	Output is correct
17	Correct	192 ms	43524 KB	Output is correct
18	Correct	153 ms	43520 KB	Output is correct
19	Correct	171 ms	48896 KB	Output is correct
20	Correct	239 ms	47616 KB	Output is correct
21	Correct	143 ms	42756 KB	Output is correct
22	Correct	137 ms	42748 KB	Output is correct
23	Correct	152 ms	43008 KB	Output is correct
24	Correct	156 ms	43008 KB	Output is correct
25	Correct	163 ms	47104 KB	Output is correct
26	Correct	169 ms	42540 KB	Output is correct
27	Correct	117 ms	42412 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	15612 KB	Output is correct
2	Correct	41 ms	17896 KB	Output is correct
3	Correct	43 ms	17932 KB	Output is correct
4	Correct	61 ms	18136 KB	Output is correct
5	Correct	58 ms	18476 KB	Output is correct
6	Correct	41 ms	17780 KB	Output is correct
7	Correct	32 ms	15628 KB	Output is correct
8	Correct	130 ms	42612 KB	Output is correct
9	Correct	158 ms	42608 KB	Output is correct
10	Correct	29 ms	15612 KB	Output is correct
11	Correct	143 ms	58592 KB	Output is correct
12	Correct	168 ms	58620 KB	Output is correct
13	Correct	148 ms	58676 KB	Output is correct
14	Correct	33 ms	15620 KB	Output is correct
15	Correct	121 ms	42756 KB	Output is correct
16	Correct	154 ms	42676 KB	Output is correct
17	Correct	192 ms	43524 KB	Output is correct
18	Correct	153 ms	43520 KB	Output is correct
19	Correct	171 ms	48896 KB	Output is correct
20	Correct	239 ms	47616 KB	Output is correct
21	Correct	143 ms	42756 KB	Output is correct
22	Correct	137 ms	42748 KB	Output is correct
23	Correct	152 ms	43008 KB	Output is correct
24	Correct	156 ms	43008 KB	Output is correct
25	Correct	163 ms	47104 KB	Output is correct
26	Correct	169 ms	42540 KB	Output is correct
27	Correct	117 ms	42412 KB	Output is correct
28	Incorrect	32 ms	15560 KB	Extra information in the output file
29	Halted	0 ms	0 KB	-

Submission #934182

Compilation message