Submission #934169

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934169	2024-02-26T22:50:58 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	50 / 100	339 ms	118012 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 || u==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]] || up[0][mid]==0||mid==0);
		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];
		}
		

		u = a;
		int v = -1;
		for (int d = 17; d >= 0; d--)
		{
			if (!isancestor(up[d][u], b))
			{
				good &= upincreasing[d][u];
				u = up[d][u];
			}
		}

		if (!isancestor(u, b))
		{
			v = upmax[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	40 ms	89336 KB	Output is correct
2	Correct	51 ms	89600 KB	Output is correct
3	Correct	57 ms	89848 KB	Output is correct
4	Correct	61 ms	88032 KB	Output is correct
5	Correct	69 ms	88064 KB	Output is correct
6	Correct	50 ms	85764 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	89336 KB	Output is correct
2	Correct	51 ms	89600 KB	Output is correct
3	Correct	57 ms	89848 KB	Output is correct
4	Correct	61 ms	88032 KB	Output is correct
5	Correct	69 ms	88064 KB	Output is correct
6	Correct	50 ms	85764 KB	Output is correct
7	Incorrect	39 ms	87040 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	42 ms	89348 KB	Output is correct
2	Correct	202 ms	103788 KB	Output is correct
3	Correct	194 ms	104028 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	89348 KB	Output is correct
2	Correct	202 ms	103788 KB	Output is correct
3	Correct	194 ms	104028 KB	Output is correct
4	Incorrect	36 ms	87300 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	39 ms	87292 KB	Output is correct
2	Correct	171 ms	116964 KB	Output is correct
3	Correct	160 ms	117624 KB	Output is correct
4	Correct	211 ms	117180 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	87292 KB	Output is correct
2	Correct	171 ms	116964 KB	Output is correct
3	Correct	160 ms	117624 KB	Output is correct
4	Correct	211 ms	117180 KB	Output is correct
5	Incorrect	39 ms	87032 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	49 ms	87292 KB	Output is correct
2	Correct	150 ms	104192 KB	Output is correct
3	Correct	177 ms	104748 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	87292 KB	Output is correct
2	Correct	150 ms	104192 KB	Output is correct
3	Correct	177 ms	104748 KB	Output is correct
4	Incorrect	37 ms	87044 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	37 ms	89356 KB	Output is correct
2	Correct	212 ms	117924 KB	Output is correct
3	Correct	175 ms	117384 KB	Output is correct
4	Correct	210 ms	117016 KB	Output is correct
5	Correct	37 ms	87296 KB	Output is correct
6	Correct	138 ms	104836 KB	Output is correct
7	Correct	163 ms	105060 KB	Output is correct
8	Correct	287 ms	105808 KB	Output is correct
9	Correct	238 ms	105904 KB	Output is correct
10	Correct	267 ms	111616 KB	Output is correct
11	Correct	338 ms	110472 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	89356 KB	Output is correct
2	Correct	212 ms	117924 KB	Output is correct
3	Correct	175 ms	117384 KB	Output is correct
4	Correct	210 ms	117016 KB	Output is correct
5	Correct	37 ms	87296 KB	Output is correct
6	Correct	138 ms	104836 KB	Output is correct
7	Correct	163 ms	105060 KB	Output is correct
8	Correct	287 ms	105808 KB	Output is correct
9	Correct	238 ms	105904 KB	Output is correct
10	Correct	267 ms	111616 KB	Output is correct
11	Correct	338 ms	110472 KB	Output is correct
12	Incorrect	34 ms	88064 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	39 ms	89344 KB	Output is correct
2	Correct	52 ms	89756 KB	Output is correct
3	Correct	52 ms	89856 KB	Output is correct
4	Correct	71 ms	87896 KB	Output is correct
5	Correct	71 ms	90104 KB	Output is correct
6	Correct	51 ms	87812 KB	Output is correct
7	Correct	37 ms	87304 KB	Output is correct
8	Correct	209 ms	102972 KB	Output is correct
9	Correct	205 ms	103740 KB	Output is correct
10	Correct	34 ms	87296 KB	Output is correct
11	Correct	174 ms	118012 KB	Output is correct
12	Correct	167 ms	117248 KB	Output is correct
13	Correct	197 ms	116940 KB	Output is correct
14	Correct	42 ms	87144 KB	Output is correct
15	Correct	143 ms	104160 KB	Output is correct
16	Correct	176 ms	104412 KB	Output is correct
17	Correct	270 ms	105984 KB	Output is correct
18	Correct	236 ms	104708 KB	Output is correct
19	Correct	261 ms	111552 KB	Output is correct
20	Correct	339 ms	110400 KB	Output is correct
21	Correct	202 ms	106808 KB	Output is correct
22	Correct	236 ms	107516 KB	Output is correct
23	Correct	217 ms	108020 KB	Output is correct
24	Correct	235 ms	108156 KB	Output is correct
25	Correct	231 ms	111212 KB	Output is correct
26	Correct	187 ms	108032 KB	Output is correct
27	Correct	172 ms	107236 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	89344 KB	Output is correct
2	Correct	52 ms	89756 KB	Output is correct
3	Correct	52 ms	89856 KB	Output is correct
4	Correct	71 ms	87896 KB	Output is correct
5	Correct	71 ms	90104 KB	Output is correct
6	Correct	51 ms	87812 KB	Output is correct
7	Correct	37 ms	87304 KB	Output is correct
8	Correct	209 ms	102972 KB	Output is correct
9	Correct	205 ms	103740 KB	Output is correct
10	Correct	34 ms	87296 KB	Output is correct
11	Correct	174 ms	118012 KB	Output is correct
12	Correct	167 ms	117248 KB	Output is correct
13	Correct	197 ms	116940 KB	Output is correct
14	Correct	42 ms	87144 KB	Output is correct
15	Correct	143 ms	104160 KB	Output is correct
16	Correct	176 ms	104412 KB	Output is correct
17	Correct	270 ms	105984 KB	Output is correct
18	Correct	236 ms	104708 KB	Output is correct
19	Correct	261 ms	111552 KB	Output is correct
20	Correct	339 ms	110400 KB	Output is correct
21	Correct	202 ms	106808 KB	Output is correct
22	Correct	236 ms	107516 KB	Output is correct
23	Correct	217 ms	108020 KB	Output is correct
24	Correct	235 ms	108156 KB	Output is correct
25	Correct	231 ms	111212 KB	Output is correct
26	Correct	187 ms	108032 KB	Output is correct
27	Correct	172 ms	107236 KB	Output is correct
28	Incorrect	40 ms	88068 KB	Extra information in the output file
29	Halted	0 ms	0 KB	-

Submission #934169

Compilation message