oj.uz

Submission #934221

# Submission time Handle Problem Language Result Execution time Memory
934221 2024-02-27T02:12:59 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 72648 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];
int depth[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	depth[u] = depth[p] + 1;
	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);
	vector<p2> edgelist;
	rep(i, n + q - 1)
	{
		char c;
		cin >> c;
		if (c=='S')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			edgelist.push_back(p2(a, b));
			edges[a].push_back(p2(b, t));
			edges[b].push_back(p2(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 });
		}
	}
	depth[0] = 0;
	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);
	};

	vector<map<int,int>> children(n);
	vi sum(n);
	vvi blocked(n);
	rep(i, n)blocked[i].push_back(inf);
	vi parenton(n);

	auto enable = [&](int ind)
	{
		int u = depth[edgelist[ind].first] > depth[edgelist[ind].second] ? edgelist[ind].first : edgelist[ind].second;
		parenton[u] = 1;
		while (true)
		{
			if (!parenton[u]) break;
			if (u == 0) break;
			repe(c, blocked[u])
			{
				if (c>upv[u])
				{
					children[up[u][0]][upv[u]]++;
					blocked[up[u][0]].push_back(upv[u]);
				}
			}
			blocked[u] = vi();
			u = up[u][0];
		}
		
	};

	int timer = 0;
	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
		{
			
			while (timer<=t)
			{
				enable(timer++);
			}
			
			int ans = 0;
			repe(c, children[a]) ans += c.second;
			int u=a;
			int prev = upv[a];
			
			while (u!=0)
			{
				u = up[u][0];
				if (!pathgood(a, u, t)) break;
				ans++;
				repe(c, children[u]) if (c.first > prev) ans += c.second;
				prev = u;
				if (u == 0)
				{
					
					break;
				}
			}

			cout << ans+1 << "\n";
		}
	}

	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13580 KB Output is correct
2 Correct 46 ms 14440 KB Output is correct
3 Correct 41 ms 14480 KB Output is correct
4 Correct 56 ms 14588 KB Output is correct
5 Correct 69 ms 15104 KB Output is correct
6 Correct 62 ms 14624 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13580 KB Output is correct
2 Correct 46 ms 14440 KB Output is correct
3 Correct 41 ms 14480 KB Output is correct
4 Correct 56 ms 14588 KB Output is correct
5 Correct 69 ms 15104 KB Output is correct
6 Correct 62 ms 14624 KB Output is correct
7 Incorrect 35 ms 13568 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 31 ms 13576 KB Output is correct
2 Correct 139 ms 56636 KB Output is correct
3 Correct 139 ms 56596 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13576 KB Output is correct
2 Correct 139 ms 56636 KB Output is correct
3 Correct 139 ms 56596 KB Output is correct
4 Correct 37 ms 13568 KB Output is correct
5 Execution timed out 3571 ms 59228 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13572 KB Output is correct
2 Correct 154 ms 72564 KB Output is correct
3 Correct 157 ms 72648 KB Output is correct
4 Correct 177 ms 72564 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13572 KB Output is correct
2 Correct 154 ms 72564 KB Output is correct
3 Correct 157 ms 72648 KB Output is correct
4 Correct 177 ms 72564 KB Output is correct
5 Incorrect 29 ms 13568 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 32 ms 13568 KB Output is correct
2 Correct 127 ms 56436 KB Output is correct
3 Correct 151 ms 56636 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13568 KB Output is correct
2 Correct 127 ms 56436 KB Output is correct
3 Correct 151 ms 56636 KB Output is correct
4 Incorrect 33 ms 13380 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 29 ms 13408 KB Output is correct
2 Correct 156 ms 72396 KB Output is correct
3 Correct 159 ms 72628 KB Output is correct
4 Correct 156 ms 72588 KB Output is correct
5 Correct 33 ms 13664 KB Output is correct
6 Correct 131 ms 56556 KB Output is correct
7 Correct 137 ms 56480 KB Output is correct
8 Correct 179 ms 57264 KB Output is correct
9 Correct 158 ms 57464 KB Output is correct
10 Correct 171 ms 62868 KB Output is correct
11 Correct 233 ms 61652 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13408 KB Output is correct
2 Correct 156 ms 72396 KB Output is correct
3 Correct 159 ms 72628 KB Output is correct
4 Correct 156 ms 72588 KB Output is correct
5 Correct 33 ms 13664 KB Output is correct
6 Correct 131 ms 56556 KB Output is correct
7 Correct 137 ms 56480 KB Output is correct
8 Correct 179 ms 57264 KB Output is correct
9 Correct 158 ms 57464 KB Output is correct
10 Correct 171 ms 62868 KB Output is correct
11 Correct 233 ms 61652 KB Output is correct
12 Incorrect 28 ms 13576 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 32 ms 13364 KB Output is correct
2 Correct 41 ms 14412 KB Output is correct
3 Correct 46 ms 14504 KB Output is correct
4 Correct 48 ms 14744 KB Output is correct
5 Correct 58 ms 15144 KB Output is correct
6 Correct 41 ms 14588 KB Output is correct
7 Correct 30 ms 13568 KB Output is correct
8 Correct 162 ms 56616 KB Output is correct
9 Correct 140 ms 56508 KB Output is correct
10 Correct 27 ms 13580 KB Output is correct
11 Correct 159 ms 72568 KB Output is correct
12 Correct 149 ms 72592 KB Output is correct
13 Correct 150 ms 72520 KB Output is correct
14 Correct 34 ms 13392 KB Output is correct
15 Correct 155 ms 56964 KB Output is correct
16 Correct 139 ms 56596 KB Output is correct
17 Correct 176 ms 57380 KB Output is correct
18 Correct 173 ms 57464 KB Output is correct
19 Correct 173 ms 62840 KB Output is correct
20 Correct 220 ms 61556 KB Output is correct
21 Correct 144 ms 56568 KB Output is correct
22 Correct 150 ms 56568 KB Output is correct
23 Correct 149 ms 57204 KB Output is correct
24 Correct 151 ms 56956 KB Output is correct
25 Correct 181 ms 60888 KB Output is correct
26 Correct 134 ms 56252 KB Output is correct
27 Correct 127 ms 56492 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13364 KB Output is correct
2 Correct 41 ms 14412 KB Output is correct
3 Correct 46 ms 14504 KB Output is correct
4 Correct 48 ms 14744 KB Output is correct
5 Correct 58 ms 15144 KB Output is correct
6 Correct 41 ms 14588 KB Output is correct
7 Correct 30 ms 13568 KB Output is correct
8 Correct 162 ms 56616 KB Output is correct
9 Correct 140 ms 56508 KB Output is correct
10 Correct 27 ms 13580 KB Output is correct
11 Correct 159 ms 72568 KB Output is correct
12 Correct 149 ms 72592 KB Output is correct
13 Correct 150 ms 72520 KB Output is correct
14 Correct 34 ms 13392 KB Output is correct
15 Correct 155 ms 56964 KB Output is correct
16 Correct 139 ms 56596 KB Output is correct
17 Correct 176 ms 57380 KB Output is correct
18 Correct 173 ms 57464 KB Output is correct
19 Correct 173 ms 62840 KB Output is correct
20 Correct 220 ms 61556 KB Output is correct
21 Correct 144 ms 56568 KB Output is correct
22 Correct 150 ms 56568 KB Output is correct
23 Correct 149 ms 57204 KB Output is correct
24 Correct 151 ms 56956 KB Output is correct
25 Correct 181 ms 60888 KB Output is correct
26 Correct 134 ms 56252 KB Output is correct
27 Correct 127 ms 56492 KB Output is correct
28 Incorrect 34 ms 13576 KB Extra information in the output file
29 Halted 0 ms 0 KB -