oj.uz

Submission #934220

# Submission time Handle Problem Language Result Execution time Memory
934220 2024-02-27T02:06:02 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 72756 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;
		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 32 ms 13556 KB Output is correct
2 Correct 41 ms 14588 KB Output is correct
3 Correct 41 ms 14484 KB Output is correct
4 Correct 48 ms 14596 KB Output is correct
5 Correct 57 ms 15040 KB Output is correct
6 Correct 39 ms 14592 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13556 KB Output is correct
2 Correct 41 ms 14588 KB Output is correct
3 Correct 41 ms 14484 KB Output is correct
4 Correct 48 ms 14596 KB Output is correct
5 Correct 57 ms 15040 KB Output is correct
6 Correct 39 ms 14592 KB Output is correct
7 Incorrect 33 ms 13564 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 13572 KB Output is correct
2 Correct 148 ms 57064 KB Output is correct
3 Correct 138 ms 56548 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13572 KB Output is correct
2 Correct 148 ms 57064 KB Output is correct
3 Correct 138 ms 56548 KB Output is correct
4 Correct 32 ms 13580 KB Output is correct
5 Execution timed out 3509 ms 62156 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 13432 KB Output is correct
2 Correct 153 ms 72436 KB Output is correct
3 Correct 158 ms 72604 KB Output is correct
4 Correct 148 ms 72568 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13432 KB Output is correct
2 Correct 153 ms 72436 KB Output is correct
3 Correct 158 ms 72604 KB Output is correct
4 Correct 148 ms 72568 KB Output is correct
5 Incorrect 31 ms 13580 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 31 ms 13576 KB Output is correct
2 Correct 126 ms 56440 KB Output is correct
3 Correct 134 ms 56468 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13576 KB Output is correct
2 Correct 126 ms 56440 KB Output is correct
3 Correct 134 ms 56468 KB Output is correct
4 Incorrect 31 ms 13568 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 27 ms 13568 KB Output is correct
2 Correct 168 ms 72564 KB Output is correct
3 Correct 150 ms 72508 KB Output is correct
4 Correct 147 ms 72564 KB Output is correct
5 Correct 32 ms 13472 KB Output is correct
6 Correct 120 ms 56432 KB Output is correct
7 Correct 143 ms 56632 KB Output is correct
8 Correct 176 ms 57280 KB Output is correct
9 Correct 163 ms 57464 KB Output is correct
10 Correct 176 ms 62820 KB Output is correct
11 Correct 211 ms 61524 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13568 KB Output is correct
2 Correct 168 ms 72564 KB Output is correct
3 Correct 150 ms 72508 KB Output is correct
4 Correct 147 ms 72564 KB Output is correct
5 Correct 32 ms 13472 KB Output is correct
6 Correct 120 ms 56432 KB Output is correct
7 Correct 143 ms 56632 KB Output is correct
8 Correct 176 ms 57280 KB Output is correct
9 Correct 163 ms 57464 KB Output is correct
10 Correct 176 ms 62820 KB Output is correct
11 Correct 211 ms 61524 KB Output is correct
12 Incorrect 37 ms 13460 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 13580 KB Output is correct
2 Correct 41 ms 14600 KB Output is correct
3 Correct 40 ms 14592 KB Output is correct
4 Correct 49 ms 14596 KB Output is correct
5 Correct 58 ms 15104 KB Output is correct
6 Correct 40 ms 14600 KB Output is correct
7 Correct 31 ms 13564 KB Output is correct
8 Correct 128 ms 56552 KB Output is correct
9 Correct 137 ms 56660 KB Output is correct
10 Correct 28 ms 13472 KB Output is correct
11 Correct 149 ms 72568 KB Output is correct
12 Correct 144 ms 72568 KB Output is correct
13 Correct 162 ms 72756 KB Output is correct
14 Correct 31 ms 13580 KB Output is correct
15 Correct 127 ms 56380 KB Output is correct
16 Correct 138 ms 56484 KB Output is correct
17 Correct 197 ms 57348 KB Output is correct
18 Correct 173 ms 57464 KB Output is correct
19 Correct 178 ms 62804 KB Output is correct
20 Correct 234 ms 61480 KB Output is correct
21 Correct 152 ms 56568 KB Output is correct
22 Correct 138 ms 56600 KB Output is correct
23 Correct 146 ms 56948 KB Output is correct
24 Correct 141 ms 56876 KB Output is correct
25 Correct 181 ms 60732 KB Output is correct
26 Correct 145 ms 56380 KB Output is correct
27 Correct 125 ms 56252 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13580 KB Output is correct
2 Correct 41 ms 14600 KB Output is correct
3 Correct 40 ms 14592 KB Output is correct
4 Correct 49 ms 14596 KB Output is correct
5 Correct 58 ms 15104 KB Output is correct
6 Correct 40 ms 14600 KB Output is correct
7 Correct 31 ms 13564 KB Output is correct
8 Correct 128 ms 56552 KB Output is correct
9 Correct 137 ms 56660 KB Output is correct
10 Correct 28 ms 13472 KB Output is correct
11 Correct 149 ms 72568 KB Output is correct
12 Correct 144 ms 72568 KB Output is correct
13 Correct 162 ms 72756 KB Output is correct
14 Correct 31 ms 13580 KB Output is correct
15 Correct 127 ms 56380 KB Output is correct
16 Correct 138 ms 56484 KB Output is correct
17 Correct 197 ms 57348 KB Output is correct
18 Correct 173 ms 57464 KB Output is correct
19 Correct 178 ms 62804 KB Output is correct
20 Correct 234 ms 61480 KB Output is correct
21 Correct 152 ms 56568 KB Output is correct
22 Correct 138 ms 56600 KB Output is correct
23 Correct 146 ms 56948 KB Output is correct
24 Correct 141 ms 56876 KB Output is correct
25 Correct 181 ms 60732 KB Output is correct
26 Correct 145 ms 56380 KB Output is correct
27 Correct 125 ms 56252 KB Output is correct
28 Incorrect 34 ms 13572 KB Extra information in the output file
29 Halted 0 ms 0 KB -