Submission #934159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934159	2024-02-26T22:05:26 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	15 / 100	3500 ms	75028 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[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;
}

Subtask #1
2.5 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
2.5 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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

Submission #934159

Compilation message