oj.uz

Submission #934217

# Submission time Handle Problem Language Result Execution time Memory
934217 2024-02-27T01:55:57 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 240 ms 76324 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].first] ? edgelist[ind].first : edgelist[ind].second;
		while (true)
		{
			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 33 ms 14332 KB Output is correct
2 Correct 41 ms 15876 KB Output is correct
3 Correct 43 ms 15868 KB Output is correct
4 Correct 51 ms 16036 KB Output is correct
5 Correct 61 ms 16744 KB Output is correct
6 Correct 42 ms 16000 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14332 KB Output is correct
2 Correct 41 ms 15876 KB Output is correct
3 Correct 43 ms 15868 KB Output is correct
4 Correct 51 ms 16036 KB Output is correct
5 Correct 61 ms 16744 KB Output is correct
6 Correct 42 ms 16000 KB Output is correct
7 Incorrect 35 ms 14336 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 33 ms 14420 KB Output is correct
2 Correct 141 ms 59372 KB Output is correct
3 Correct 140 ms 59112 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14420 KB Output is correct
2 Correct 141 ms 59372 KB Output is correct
3 Correct 140 ms 59112 KB Output is correct
4 Incorrect 33 ms 14336 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 30 ms 14344 KB Output is correct
2 Correct 169 ms 76324 KB Output is correct
3 Correct 156 ms 75876 KB Output is correct
4 Correct 155 ms 75672 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14344 KB Output is correct
2 Correct 169 ms 76324 KB Output is correct
3 Correct 156 ms 75876 KB Output is correct
4 Correct 155 ms 75672 KB Output is correct
5 Incorrect 30 ms 14212 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 37 ms 13376 KB Output is correct
2 Correct 127 ms 56536 KB Output is correct
3 Correct 156 ms 56712 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13376 KB Output is correct
2 Correct 127 ms 56536 KB Output is correct
3 Correct 156 ms 56712 KB Output is correct
4 Incorrect 35 ms 13348 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 13440 KB Output is correct
2 Correct 152 ms 75856 KB Output is correct
3 Correct 168 ms 75788 KB Output is correct
4 Correct 156 ms 75712 KB Output is correct
5 Correct 35 ms 14320 KB Output is correct
6 Correct 123 ms 59768 KB Output is correct
7 Correct 139 ms 59704 KB Output is correct
8 Correct 188 ms 60704 KB Output is correct
9 Correct 167 ms 60552 KB Output is correct
10 Correct 178 ms 66164 KB Output is correct
11 Correct 240 ms 65320 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13440 KB Output is correct
2 Correct 152 ms 75856 KB Output is correct
3 Correct 168 ms 75788 KB Output is correct
4 Correct 156 ms 75712 KB Output is correct
5 Correct 35 ms 14320 KB Output is correct
6 Correct 123 ms 59768 KB Output is correct
7 Correct 139 ms 59704 KB Output is correct
8 Correct 188 ms 60704 KB Output is correct
9 Correct 167 ms 60552 KB Output is correct
10 Correct 178 ms 66164 KB Output is correct
11 Correct 240 ms 65320 KB Output is correct
12 Incorrect 30 ms 14332 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 33 ms 13564 KB Output is correct
2 Correct 42 ms 14624 KB Output is correct
3 Correct 42 ms 14712 KB Output is correct
4 Correct 56 ms 14668 KB Output is correct
5 Correct 58 ms 15084 KB Output is correct
6 Correct 42 ms 14844 KB Output is correct
7 Correct 33 ms 13568 KB Output is correct
8 Correct 141 ms 56516 KB Output is correct
9 Correct 132 ms 56556 KB Output is correct
10 Correct 31 ms 13576 KB Output is correct
11 Correct 169 ms 75924 KB Output is correct
12 Correct 153 ms 75896 KB Output is correct
13 Correct 166 ms 75636 KB Output is correct
14 Correct 33 ms 14588 KB Output is correct
15 Correct 126 ms 59768 KB Output is correct
16 Correct 154 ms 60120 KB Output is correct
17 Correct 185 ms 61188 KB Output is correct
18 Correct 161 ms 60536 KB Output is correct
19 Correct 185 ms 66208 KB Output is correct
20 Correct 231 ms 64912 KB Output is correct
21 Correct 152 ms 59928 KB Output is correct
22 Correct 148 ms 60460 KB Output is correct
23 Correct 156 ms 60260 KB Output is correct
24 Correct 166 ms 60556 KB Output is correct
25 Correct 179 ms 64520 KB Output is correct
26 Correct 134 ms 59828 KB Output is correct
27 Correct 131 ms 59840 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13564 KB Output is correct
2 Correct 42 ms 14624 KB Output is correct
3 Correct 42 ms 14712 KB Output is correct
4 Correct 56 ms 14668 KB Output is correct
5 Correct 58 ms 15084 KB Output is correct
6 Correct 42 ms 14844 KB Output is correct
7 Correct 33 ms 13568 KB Output is correct
8 Correct 141 ms 56516 KB Output is correct
9 Correct 132 ms 56556 KB Output is correct
10 Correct 31 ms 13576 KB Output is correct
11 Correct 169 ms 75924 KB Output is correct
12 Correct 153 ms 75896 KB Output is correct
13 Correct 166 ms 75636 KB Output is correct
14 Correct 33 ms 14588 KB Output is correct
15 Correct 126 ms 59768 KB Output is correct
16 Correct 154 ms 60120 KB Output is correct
17 Correct 185 ms 61188 KB Output is correct
18 Correct 161 ms 60536 KB Output is correct
19 Correct 185 ms 66208 KB Output is correct
20 Correct 231 ms 64912 KB Output is correct
21 Correct 152 ms 59928 KB Output is correct
22 Correct 148 ms 60460 KB Output is correct
23 Correct 156 ms 60260 KB Output is correct
24 Correct 166 ms 60556 KB Output is correct
25 Correct 179 ms 64520 KB Output is correct
26 Correct 134 ms 59828 KB Output is correct
27 Correct 131 ms 59840 KB Output is correct
28 Incorrect 35 ms 14344 KB Extra information in the output file
29 Halted 0 ms 0 KB -