Submission #934142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934142	2024-02-26T21:36:12 Z	Joshua_Andersson	Inside information (BOI21_servers)	C++14	15 / 100	3500 ms	35332 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 upv[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	tin[u] = timer++;
	up[0][u] = p;
	

	repe(e, edges[u]) if (e.first != p) dfs(e.first, u, p1, _p2, edges), upv[e.first]=e.second;

	tout[u] = timer++;
}

bool isancestor(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

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 pathgood = [&](int a, int b, int t)
	{
		// 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] <= t;
			good &= upv[u] < prev;
			prev = upv[u];
			u = up[0][u];
		}
		
		u = a;
		int v = -1;
		while (!isancestor(u, b))
		{
			good &= upv[u] <= t;
			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	27 ms	11264 KB	Output is correct
2	Correct	38 ms	13064 KB	Output is correct
3	Correct	32 ms	13136 KB	Output is correct
4	Correct	386 ms	13368 KB	Output is correct
5	Correct	321 ms	13428 KB	Output is correct
6	Correct	31 ms	13064 KB	Output is correct

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	11264 KB	Output is correct
2	Correct	38 ms	13064 KB	Output is correct
3	Correct	32 ms	13136 KB	Output is correct
4	Correct	386 ms	13368 KB	Output is correct
5	Correct	321 ms	13428 KB	Output is correct
6	Correct	31 ms	13064 KB	Output is correct
7	Incorrect	28 ms	12104 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	26 ms	11272 KB	Output is correct
2	Correct	64 ms	21896 KB	Output is correct
3	Correct	67 ms	21924 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	11272 KB	Output is correct
2	Correct	64 ms	21896 KB	Output is correct
3	Correct	67 ms	21924 KB	Output is correct
4	Incorrect	25 ms	11260 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	29 ms	11184 KB	Output is correct
2	Correct	108 ms	31876 KB	Output is correct
3	Correct	100 ms	32004 KB	Output is correct
4	Execution timed out	3577 ms	31224 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	11184 KB	Output is correct
2	Correct	108 ms	31876 KB	Output is correct
3	Correct	100 ms	32004 KB	Output is correct
4	Execution timed out	3577 ms	31224 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	11264 KB	Output is correct
2	Correct	76 ms	26056 KB	Output is correct
3	Correct	107 ms	26200 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	11264 KB	Output is correct
2	Correct	76 ms	26056 KB	Output is correct
3	Correct	107 ms	26200 KB	Output is correct
4	Incorrect	28 ms	12232 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	30 ms	11296 KB	Output is correct
2	Correct	96 ms	31880 KB	Output is correct
3	Correct	103 ms	32000 KB	Output is correct
4	Execution timed out	3555 ms	31460 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	11296 KB	Output is correct
2	Correct	96 ms	31880 KB	Output is correct
3	Correct	103 ms	32000 KB	Output is correct
4	Execution timed out	3555 ms	31460 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	11260 KB	Output is correct
2	Correct	38 ms	13064 KB	Output is correct
3	Correct	31 ms	13068 KB	Output is correct
4	Correct	390 ms	13176 KB	Output is correct
5	Correct	321 ms	13552 KB	Output is correct
6	Correct	32 ms	13076 KB	Output is correct
7	Correct	25 ms	12028 KB	Output is correct
8	Correct	65 ms	24696 KB	Output is correct
9	Correct	65 ms	24688 KB	Output is correct
10	Correct	30 ms	12228 KB	Output is correct
11	Correct	126 ms	35328 KB	Output is correct
12	Correct	96 ms	35332 KB	Output is correct
13	Execution timed out	3503 ms	34684 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	11260 KB	Output is correct
2	Correct	38 ms	13064 KB	Output is correct
3	Correct	31 ms	13068 KB	Output is correct
4	Correct	390 ms	13176 KB	Output is correct
5	Correct	321 ms	13552 KB	Output is correct
6	Correct	32 ms	13076 KB	Output is correct
7	Correct	25 ms	12028 KB	Output is correct
8	Correct	65 ms	24696 KB	Output is correct
9	Correct	65 ms	24688 KB	Output is correct
10	Correct	30 ms	12228 KB	Output is correct
11	Correct	126 ms	35328 KB	Output is correct
12	Correct	96 ms	35332 KB	Output is correct
13	Execution timed out	3503 ms	34684 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Submission #934142

Compilation message