oj.uz

Submission #934198

# Submission time Handle Problem Language Result Execution time Memory
934198 2024-02-27T01:00:14 Z Joshua_Andersson Inside information (BOI21_servers) C++14
15 / 100
 1346 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//#define int ll
const int inf = int(1e9);

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[maxn][18];
bool upincreasing[maxn][18];
bool updecreasing[maxn][18];
int upmax[maxn][18];
int upv[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	tin[u] = timer++;
	up[u][0] = p;
	upmax[u][0] = upv[u];
	upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p==0 || u==0;
	updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p==0 || u==0;
	repp(d,1,18)
	{
		int mid = up[u][d - 1];
		up[u][d] = up[mid][d - 1];
		upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
		upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
		updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] ==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[a][d], b))
		{
			ret = max(ret, upmax[a][d]);
			a = up[a][d];
		}
	}
	return max(ret, upmax[a][0]);
}

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[u][d],a))
			{
				good &= updecreasing[u][d];
				u = up[u][d];
			}
		}
		if (!isancestor(u,a))
		{
			prev = upmax[u][0];
		}
		

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

		return good && (v < prev);
	};

	vvi children(n);
	rep(i, n)
	{
		int u = i;
		children[i].push_back(-1);
		if (u == 0) continue;
		while (true)
		{
			u = up[u][0];
			children[u].push_back(upv[i]);

			if (u == 0) break;
		}
	}
	rep(i, n) sort(all(children[i]));

	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";
		}
		else
		{
			int ans = 0;

			int d = 0;
			auto it = upper_bound(all(children[a]), t);
			if (it != begin(children[a])) ans += it - begin(children[a]);
			it = lower_bound(all(children[a]), upv[a]);
			d = end(children[a]) - it + 1;

			int u = a;
			int prev = upv[u];
			while (true)
			{
				u = up[u][0];
				it = lower_bound(all(children[u]), prev);
				ans += end(children[u])-it;
				ans -= d;
				it = lower_bound(all(children[u]), upv[u]);
				d = end(children[u])-it+1;
				if (u == 0) break;
				if (upv[u] < prev) break;
				if (upv[u] > t) break;
				prev = upv[u];
				u = up[u][0];
			}
			cout << ans+1 << "\n";
		}
	}

	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16564 KB Output is correct
2 Correct 42 ms 19712 KB Output is correct
3 Correct 42 ms 19708 KB Output is correct
4 Correct 162 ms 33128 KB Output is correct
5 Correct 447 ms 60060 KB Output is correct
6 Correct 41 ms 19468 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16564 KB Output is correct
2 Correct 42 ms 19712 KB Output is correct
3 Correct 42 ms 19708 KB Output is correct
4 Correct 162 ms 33128 KB Output is correct
5 Correct 447 ms 60060 KB Output is correct
6 Correct 41 ms 19468 KB Output is correct
7 Incorrect 35 ms 16396 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 32 ms 16440 KB Output is correct
2 Correct 137 ms 52364 KB Output is correct
3 Correct 150 ms 52480 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16440 KB Output is correct
2 Correct 137 ms 52364 KB Output is correct
3 Correct 150 ms 52480 KB Output is correct
4 Incorrect 33 ms 16636 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 28 ms 16316 KB Output is correct
2 Runtime error 1346 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16316 KB Output is correct
2 Runtime error 1346 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16392 KB Output is correct
2 Correct 161 ms 59136 KB Output is correct
3 Correct 221 ms 59132 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16392 KB Output is correct
2 Correct 161 ms 59136 KB Output is correct
3 Correct 221 ms 59132 KB Output is correct
4 Incorrect 35 ms 16636 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 28 ms 16384 KB Output is correct
2 Runtime error 1276 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16384 KB Output is correct
2 Runtime error 1276 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16420 KB Output is correct
2 Correct 43 ms 19708 KB Output is correct
3 Correct 43 ms 19712 KB Output is correct
4 Correct 163 ms 32764 KB Output is correct
5 Correct 476 ms 60072 KB Output is correct
6 Correct 44 ms 19468 KB Output is correct
7 Correct 32 ms 16452 KB Output is correct
8 Correct 145 ms 52980 KB Output is correct
9 Correct 139 ms 52764 KB Output is correct
10 Correct 27 ms 16392 KB Output is correct
11 Runtime error 1300 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16420 KB Output is correct
2 Correct 43 ms 19708 KB Output is correct
3 Correct 43 ms 19712 KB Output is correct
4 Correct 163 ms 32764 KB Output is correct
5 Correct 476 ms 60072 KB Output is correct
6 Correct 44 ms 19468 KB Output is correct
7 Correct 32 ms 16452 KB Output is correct
8 Correct 145 ms 52980 KB Output is correct
9 Correct 139 ms 52764 KB Output is correct
10 Correct 27 ms 16392 KB Output is correct
11 Runtime error 1300 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -