Submission #934162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934162	2024-02-26T22:27:04 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	15 / 100	3500 ms	77732 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];
bool upincreasing[18][maxn];
//int updown[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];
	upincreasing[0][u] = upmax[0][u] < upmax[0][p];
	repp(d,1,18)
	{
		int mid = up[d - 1][u];
		up[d][u] = up[d - 1][mid];
		upmax[d][u] = max(upmax[d - 1][u], upmax[d - 1][mid]);
		upincreasing[d][u] = upincreasing[d - 1][u] && upincreasing[d-1][mid] && (upmax[0][mid] < upmax[0][up[0][mid]]);
	}
	

	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	34 ms	54284 KB	Output is correct
2	Correct	46 ms	54776 KB	Output is correct
3	Correct	40 ms	54800 KB	Output is correct
4	Correct	56 ms	54792 KB	Output is correct
5	Correct	345 ms	55152 KB	Output is correct
6	Correct	41 ms	54784 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	54284 KB	Output is correct
2	Correct	46 ms	54776 KB	Output is correct
3	Correct	40 ms	54800 KB	Output is correct
4	Correct	56 ms	54792 KB	Output is correct
5	Correct	345 ms	55152 KB	Output is correct
6	Correct	41 ms	54784 KB	Output is correct
7	Incorrect	34 ms	54536 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	35 ms	54296 KB	Output is correct
2	Correct	168 ms	65424 KB	Output is correct
3	Correct	191 ms	65320 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	54296 KB	Output is correct
2	Correct	168 ms	65424 KB	Output is correct
3	Correct	191 ms	65320 KB	Output is correct
4	Incorrect	32 ms	54280 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	32 ms	54284 KB	Output is correct
2	Correct	147 ms	77500 KB	Output is correct
3	Correct	138 ms	77732 KB	Output is correct
4	Execution timed out	3534 ms	76612 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	54284 KB	Output is correct
2	Correct	147 ms	77500 KB	Output is correct
3	Correct	138 ms	77732 KB	Output is correct
4	Execution timed out	3534 ms	76612 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	54280 KB	Output is correct
2	Correct	136 ms	66616 KB	Output is correct
3	Correct	163 ms	66332 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	54280 KB	Output is correct
2	Correct	136 ms	66616 KB	Output is correct
3	Correct	163 ms	66332 KB	Output is correct
4	Incorrect	33 ms	54264 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	31 ms	54284 KB	Output is correct
2	Correct	152 ms	77660 KB	Output is correct
3	Correct	137 ms	77432 KB	Output is correct
4	Execution timed out	3588 ms	77092 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	54284 KB	Output is correct
2	Correct	152 ms	77660 KB	Output is correct
3	Correct	137 ms	77432 KB	Output is correct
4	Execution timed out	3588 ms	77092 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	54404 KB	Output is correct
2	Correct	48 ms	54780 KB	Output is correct
3	Correct	39 ms	54780 KB	Output is correct
4	Correct	61 ms	54776 KB	Output is correct
5	Correct	338 ms	55032 KB	Output is correct
6	Correct	53 ms	54784 KB	Output is correct
7	Correct	32 ms	54276 KB	Output is correct
8	Correct	160 ms	65784 KB	Output is correct
9	Correct	147 ms	65392 KB	Output is correct
10	Correct	32 ms	54616 KB	Output is correct
11	Correct	146 ms	77504 KB	Output is correct
12	Correct	153 ms	77528 KB	Output is correct
13	Execution timed out	3532 ms	76788 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	54404 KB	Output is correct
2	Correct	48 ms	54780 KB	Output is correct
3	Correct	39 ms	54780 KB	Output is correct
4	Correct	61 ms	54776 KB	Output is correct
5	Correct	338 ms	55032 KB	Output is correct
6	Correct	53 ms	54784 KB	Output is correct
7	Correct	32 ms	54276 KB	Output is correct
8	Correct	160 ms	65784 KB	Output is correct
9	Correct	147 ms	65392 KB	Output is correct
10	Correct	32 ms	54616 KB	Output is correct
11	Correct	146 ms	77504 KB	Output is correct
12	Correct	153 ms	77528 KB	Output is correct
13	Execution timed out	3532 ms	76788 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Submission #934162

Compilation message