Submission #934166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934166	2024-02-26T22:47:41 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	20 / 100	3500 ms	118684 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 upincreasing[18][maxn];
int updecreasing[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] || p==0;
	updecreasing[0][u] = upmax[0][u] > upmax[0][p] || p==0 || u==0;
	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]]);
		updecreasing[d][u] = updecreasing[d - 1][u] && updecreasing[d-1][mid] && (upmax[0][mid] > upmax[0][up[0][mid]] || up[0][mid]==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[d][a], b))
		{
			ret = max(ret, upmax[d][a]);
			a = up[d][a];
		}
	}
	return max(ret, upmax[0][a]);
}

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[d][u],a))
			{
				good &= updecreasing[d][u];
				u = up[d][u];
			}
		}
		
		if (!isancestor(u,a))
		{
			prev = upmax[0][u];
		}
		/*bool g = 1;
		int p = inf;
		while (!isancestor(u, a))
		{
			g &= upv[u] < p;
			p = upv[u];
			u = up[0][u];
		}*/
		//assert(prev == p);
		//assert(g == good);

		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	87080 KB	Output is correct
2	Correct	50 ms	85800 KB	Output is correct
3	Correct	47 ms	89852 KB	Output is correct
4	Correct	60 ms	89932 KB	Output is correct
5	Correct	209 ms	92152 KB	Output is correct
6	Correct	46 ms	91660 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	87080 KB	Output is correct
2	Correct	50 ms	85800 KB	Output is correct
3	Correct	47 ms	89852 KB	Output is correct
4	Correct	60 ms	89932 KB	Output is correct
5	Correct	209 ms	92152 KB	Output is correct
6	Correct	46 ms	91660 KB	Output is correct
7	Incorrect	39 ms	93196 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	37 ms	91168 KB	Output is correct
2	Correct	205 ms	104016 KB	Output is correct
3	Correct	186 ms	104844 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	91168 KB	Output is correct
2	Correct	205 ms	104016 KB	Output is correct
3	Correct	186 ms	104844 KB	Output is correct
4	Incorrect	37 ms	93304 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	37 ms	91140 KB	Output is correct
2	Correct	164 ms	117668 KB	Output is correct
3	Correct	191 ms	118472 KB	Output is correct
4	Correct	2337 ms	117260 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	91140 KB	Output is correct
2	Correct	164 ms	117668 KB	Output is correct
3	Correct	191 ms	118472 KB	Output is correct
4	Correct	2337 ms	117260 KB	Output is correct
5	Incorrect	41 ms	90108 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	39 ms	91140 KB	Output is correct
2	Correct	142 ms	104828 KB	Output is correct
3	Correct	162 ms	104960 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	91140 KB	Output is correct
2	Correct	142 ms	104828 KB	Output is correct
3	Correct	162 ms	104960 KB	Output is correct
4	Incorrect	37 ms	89240 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	37 ms	91144 KB	Output is correct
2	Correct	210 ms	117780 KB	Output is correct
3	Correct	166 ms	118296 KB	Output is correct
4	Correct	2315 ms	117628 KB	Output is correct
5	Correct	38 ms	92180 KB	Output is correct
6	Correct	151 ms	108304 KB	Output is correct
7	Correct	187 ms	108464 KB	Output is correct
8	Correct	385 ms	109700 KB	Output is correct
9	Correct	232 ms	109312 KB	Output is correct
10	Correct	1702 ms	115352 KB	Output is correct
11	Execution timed out	3562 ms	115020 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	91144 KB	Output is correct
2	Correct	210 ms	117780 KB	Output is correct
3	Correct	166 ms	118296 KB	Output is correct
4	Correct	2315 ms	117628 KB	Output is correct
5	Correct	38 ms	92180 KB	Output is correct
6	Correct	151 ms	108304 KB	Output is correct
7	Correct	187 ms	108464 KB	Output is correct
8	Correct	385 ms	109700 KB	Output is correct
9	Correct	232 ms	109312 KB	Output is correct
10	Correct	1702 ms	115352 KB	Output is correct
11	Execution timed out	3562 ms	115020 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	91156 KB	Output is correct
2	Correct	49 ms	89760 KB	Output is correct
3	Correct	46 ms	89860 KB	Output is correct
4	Correct	60 ms	91900 KB	Output is correct
5	Correct	205 ms	92156 KB	Output is correct
6	Correct	48 ms	91720 KB	Output is correct
7	Correct	37 ms	91392 KB	Output is correct
8	Correct	197 ms	104232 KB	Output is correct
9	Correct	195 ms	104052 KB	Output is correct
10	Correct	36 ms	89536 KB	Output is correct
11	Correct	173 ms	118684 KB	Output is correct
12	Correct	168 ms	117760 KB	Output is correct
13	Correct	2371 ms	117772 KB	Output is correct
14	Correct	38 ms	92164 KB	Output is correct
15	Correct	138 ms	108796 KB	Output is correct
16	Correct	162 ms	108772 KB	Output is correct
17	Correct	396 ms	109984 KB	Output is correct
18	Correct	277 ms	108748 KB	Output is correct
19	Correct	1699 ms	115648 KB	Output is correct
20	Execution timed out	3521 ms	114516 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	91156 KB	Output is correct
2	Correct	49 ms	89760 KB	Output is correct
3	Correct	46 ms	89860 KB	Output is correct
4	Correct	60 ms	91900 KB	Output is correct
5	Correct	205 ms	92156 KB	Output is correct
6	Correct	48 ms	91720 KB	Output is correct
7	Correct	37 ms	91392 KB	Output is correct
8	Correct	197 ms	104232 KB	Output is correct
9	Correct	195 ms	104052 KB	Output is correct
10	Correct	36 ms	89536 KB	Output is correct
11	Correct	173 ms	118684 KB	Output is correct
12	Correct	168 ms	117760 KB	Output is correct
13	Correct	2371 ms	117772 KB	Output is correct
14	Correct	38 ms	92164 KB	Output is correct
15	Correct	138 ms	108796 KB	Output is correct
16	Correct	162 ms	108772 KB	Output is correct
17	Correct	396 ms	109984 KB	Output is correct
18	Correct	277 ms	108748 KB	Output is correct
19	Correct	1699 ms	115648 KB	Output is correct
20	Execution timed out	3521 ms	114516 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Submission #934166

Compilation message