oj.uz

Submission #934224

# Submission time Handle Problem Language Result Execution time Memory
934224 2024-02-27T02:26:55 Z Joshua_Andersson Inside information (BOI21_servers) C++14
62.5 / 100
 3500 ms 78456 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;
			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 = upv[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 33 ms 13552 KB Output is correct
2 Correct 44 ms 14584 KB Output is correct
3 Correct 42 ms 14596 KB Output is correct
4 Correct 51 ms 14780 KB Output is correct
5 Correct 61 ms 15100 KB Output is correct
6 Correct 42 ms 14848 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13552 KB Output is correct
2 Correct 44 ms 14584 KB Output is correct
3 Correct 42 ms 14596 KB Output is correct
4 Correct 51 ms 14780 KB Output is correct
5 Correct 61 ms 15100 KB Output is correct
6 Correct 42 ms 14848 KB Output is correct
7 Correct 35 ms 13820 KB Output is correct
8 Correct 53 ms 15752 KB Output is correct
9 Correct 179 ms 15800 KB Output is correct
10 Correct 58 ms 15908 KB Output is correct
11 Correct 69 ms 16168 KB Output is correct
12 Correct 911 ms 16072 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13572 KB Output is correct
2 Correct 137 ms 56432 KB Output is correct
3 Correct 185 ms 56808 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13572 KB Output is correct
2 Correct 137 ms 56432 KB Output is correct
3 Correct 185 ms 56808 KB Output is correct
4 Correct 36 ms 13568 KB Output is correct
5 Execution timed out 3563 ms 59088 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 13576 KB Output is correct
2 Correct 172 ms 72536 KB Output is correct
3 Correct 155 ms 72484 KB Output is correct
4 Correct 176 ms 72568 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13576 KB Output is correct
2 Correct 172 ms 72536 KB Output is correct
3 Correct 155 ms 72484 KB Output is correct
4 Correct 176 ms 72568 KB Output is correct
5 Correct 30 ms 13576 KB Output is correct
6 Correct 268 ms 78440 KB Output is correct
7 Execution timed out 3588 ms 75952 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13416 KB Output is correct
2 Correct 151 ms 56444 KB Output is correct
3 Correct 145 ms 56616 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13416 KB Output is correct
2 Correct 151 ms 56444 KB Output is correct
3 Correct 145 ms 56616 KB Output is correct
4 Correct 34 ms 13560 KB Output is correct
5 Correct 241 ms 61524 KB Output is correct
6 Correct 278 ms 62456 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13576 KB Output is correct
2 Correct 211 ms 72468 KB Output is correct
3 Correct 152 ms 72632 KB Output is correct
4 Correct 162 ms 72600 KB Output is correct
5 Correct 33 ms 13580 KB Output is correct
6 Correct 154 ms 56592 KB Output is correct
7 Correct 151 ms 56636 KB Output is correct
8 Correct 189 ms 57280 KB Output is correct
9 Correct 189 ms 57448 KB Output is correct
10 Correct 180 ms 62668 KB Output is correct
11 Correct 245 ms 61484 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13576 KB Output is correct
2 Correct 211 ms 72468 KB Output is correct
3 Correct 152 ms 72632 KB Output is correct
4 Correct 162 ms 72600 KB Output is correct
5 Correct 33 ms 13580 KB Output is correct
6 Correct 154 ms 56592 KB Output is correct
7 Correct 151 ms 56636 KB Output is correct
8 Correct 189 ms 57280 KB Output is correct
9 Correct 189 ms 57448 KB Output is correct
10 Correct 180 ms 62668 KB Output is correct
11 Correct 245 ms 61484 KB Output is correct
12 Correct 31 ms 13536 KB Output is correct
13 Correct 236 ms 78456 KB Output is correct
14 Execution timed out 3568 ms 75920 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13568 KB Output is correct
2 Correct 42 ms 14596 KB Output is correct
3 Correct 42 ms 14596 KB Output is correct
4 Correct 51 ms 14776 KB Output is correct
5 Correct 71 ms 15104 KB Output is correct
6 Correct 47 ms 14848 KB Output is correct
7 Correct 31 ms 13696 KB Output is correct
8 Correct 142 ms 56452 KB Output is correct
9 Correct 132 ms 56900 KB Output is correct
10 Correct 28 ms 13568 KB Output is correct
11 Correct 151 ms 72396 KB Output is correct
12 Correct 156 ms 72488 KB Output is correct
13 Correct 162 ms 72836 KB Output is correct
14 Correct 32 ms 13568 KB Output is correct
15 Correct 146 ms 56572 KB Output is correct
16 Correct 142 ms 56636 KB Output is correct
17 Correct 198 ms 57336 KB Output is correct
18 Correct 196 ms 57320 KB Output is correct
19 Correct 187 ms 62836 KB Output is correct
20 Correct 303 ms 61812 KB Output is correct
21 Correct 146 ms 56588 KB Output is correct
22 Correct 144 ms 56620 KB Output is correct
23 Correct 157 ms 57312 KB Output is correct
24 Correct 155 ms 57004 KB Output is correct
25 Correct 166 ms 60788 KB Output is correct
26 Correct 132 ms 56252 KB Output is correct
27 Correct 130 ms 56440 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13568 KB Output is correct
2 Correct 42 ms 14596 KB Output is correct
3 Correct 42 ms 14596 KB Output is correct
4 Correct 51 ms 14776 KB Output is correct
5 Correct 71 ms 15104 KB Output is correct
6 Correct 47 ms 14848 KB Output is correct
7 Correct 31 ms 13696 KB Output is correct
8 Correct 142 ms 56452 KB Output is correct
9 Correct 132 ms 56900 KB Output is correct
10 Correct 28 ms 13568 KB Output is correct
11 Correct 151 ms 72396 KB Output is correct
12 Correct 156 ms 72488 KB Output is correct
13 Correct 162 ms 72836 KB Output is correct
14 Correct 32 ms 13568 KB Output is correct
15 Correct 146 ms 56572 KB Output is correct
16 Correct 142 ms 56636 KB Output is correct
17 Correct 198 ms 57336 KB Output is correct
18 Correct 196 ms 57320 KB Output is correct
19 Correct 187 ms 62836 KB Output is correct
20 Correct 303 ms 61812 KB Output is correct
21 Correct 146 ms 56588 KB Output is correct
22 Correct 144 ms 56620 KB Output is correct
23 Correct 157 ms 57312 KB Output is correct
24 Correct 155 ms 57004 KB Output is correct
25 Correct 166 ms 60788 KB Output is correct
26 Correct 132 ms 56252 KB Output is correct
27 Correct 130 ms 56440 KB Output is correct
28 Correct 38 ms 13572 KB Output is correct
29 Correct 49 ms 15616 KB Output is correct
30 Correct 185 ms 15812 KB Output is correct
31 Correct 54 ms 15928 KB Output is correct
32 Correct 64 ms 16128 KB Output is correct
33 Correct 898 ms 16164 KB Output is correct
34 Correct 33 ms 14348 KB Output is correct
35 Execution timed out 3570 ms 62096 KB Time limit exceeded
36 Halted 0 ms 0 KB -