oj.uz

Submission #771931

# Submission time Handle Problem Language Result Execution time Memory
771931 2023-07-03T12:19:09 Z LittleCube Inside information (BOI21_servers) C++17
50 / 100
 443 ms 94780 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define F first
#define S second
using namespace std;

int N, K, pre[120005][20], vis[120005], sz[120005], head[120005][20], ts;
pii io[120005], bin[120005][20], e[120005];
piii Q[120005];
vector<piii> update[120005];
vector<pii> E[120005];

struct BIT
{
	vector<int> bit;
	vector<int> vals;
	int id(int i, int p = 0)
	{
		return max(0, (int)(lower_bound(vals.begin(), vals.end(), i, greater<>()) - vals.begin()) + p);
	}
	void init(vector<int> val)
	{
		val.emplace_back(N + 8);
		val.emplace_back(N);
		val.emplace_back(-7);
		val.emplace_back(-8);
		sort(val.begin(), val.end(), greater<>());
		vals = val;
		bit.resize(vals.size(), 0);
	}
	int query(int k, int p)
	{
		int ans = 0;
		for (int i = id(k, p); i; i -= (i & -i))
			ans += bit[i];
		return ans;
	}
	void modify(int k)
	{
		for (int i = id(k); i < (int)bit.size(); i += (i & -i))
			bit[i]++;
	}
} bit[120005];

void calcsz(int u)
{
	vis[u] = sz[u] = 1;
	for (auto [v, w] : E[u])
		if (!vis[v])
		{
			calcsz(v);
			sz[u] += sz[v];
		}
	vis[u] = 0;
}

void init(int u, int p, int t, int c, int l)
{
	head[u][l] = c;
	update[p].emplace_back(piii(c, l, t));
	vis[u] = 1;
	for (auto [v, w] : E[u])
		if (!vis[v] && w > p)
			init(v, w, t, c, l);
	vis[u] = 0;
}

void cdec(int r, int l)
{
	int c = r;
	calcsz(r);
	{
		int u = r;
		do
		{
			c = u;
			for (auto [v, _] : E[u])
				if (sz[u] > sz[v] && sz[v] > sz[r] / 2)
				{
					u = v;
					break;
				}
		} while (u != c);
	}
	vector<int> v;
	head[c][l] = c;
	vis[c] = 1;
	for (auto [u, w] : E[c])
		if (!vis[u])
		{
			v.emplace_back(w);
			init(u, w, w, c, l);
		}
	bit[c].init(v);
	bit[c].modify(N);
	for (auto [u, w] : E[c])
		if (!vis[u])
			cdec(u, l + 1);
}

const pii no = {-8, -8},
		  bad = {-2, -2};
pii merge(pii p, pii q)
{
	if (p == no)
		return q;
	if (q == no)
		return p;
	if (p == bad || q == bad)
		return bad;
	if (p.F <= p.S && p.S <= q.F && q.F <= q.S)
		return pii(p.F, q.S);
	if (p.F >= p.S && p.S >= q.F && q.F >= q.S)
		return pii(p.F, q.S);
	return bad;
}

void dfs(int u)
{
	io[u].F = ++ts;
	for (auto [v, w] : E[u])
		if (v != pre[u][0])
		{
			pre[v][0] = u;
			bin[v][0] = pii(w, w);
			for (int p = 0; p + 1 < 20; p++)
				pre[v][p + 1] = pre[pre[v][p]][p],
						   bin[v][p + 1] = merge(bin[v][p], bin[pre[v][p]][p]);
			dfs(v);
		}
	io[u].S = ts;
}

bool ischild(int r, int c)
{
	return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

pii getpath(int u, int v)
{
	pii l = no, r = no;

	for (int p = 19; p >= 0; p--)
		if (!ischild(pre[u][p], v))
			l = merge(l, bin[u][p]), u = pre[u][p];
	if (!ischild(u, v))
		l = merge(l, bin[u][0]), u = pre[u][0];

	for (int p = 19; p >= 0; p--)
		if (!ischild(pre[v][p], u))
			r = merge(r, bin[v][p]), v = pre[v][p];
	if (!ischild(v, u))
		r = merge(r, bin[v][0]), v = pre[v][0];

	swap(r.F, r.S);

	return merge(l, r);
}

signed main()
{
	cin >> N >> K;
	for (int i = 0, j = 0; i + j < K + N - 1;)
	{
		char c;
		int a, b = 0;
		cin >> c >> a;
		if (c != 'C')
			cin >> b;

		if (c == 'S')
		{
			j++;
			e[j] = pii(a, b);
			E[a].emplace_back(pii(b, j));
			E[b].emplace_back(pii(a, j));
		}
		else
		{
			i++;
			Q[i] = piii(j, a, b);
		}
	}
	for (int p = 0; p < 20; p++)
		pre[1][p] = 1, bin[1][p] = no;
	dfs(1);
	cdec(1, 1);
	for (int i = 1, j = 0; i <= K; i++)
	{
		auto [t, a, b] = Q[i];
		while (j < t)
		{
			j++;
			for (auto [c, l, w] : update[j])
			{
				// cerr << "update " << j << ' ' << c << ' ' << w << '\n';
				bit[c].modify(w);
			}
		}
		if (b > 0)
		{
			int u = a, v = b;
			pii l = no, r = no;

			// cerr << merge(l, r).F << ' ' << merge(l, r).S << '\n';
			l = merge(merge(pii(t, t), getpath(a, b)), pii(0, 0));
			cout << (l != bad ? "yes\n" : "no\n");
		}
		else
		{
			int ans = 0;
			for (int p = 1; head[a][p]; p++)
			{
				int c = head[a][p];
				pii path = getpath(a, c);
				// cerr << a << ' ' << c << ' ' << path.F << ' ' << path.S << '\n';
				if (path == bad || path.F > path.S)
					continue;
				int k = path.S;
				// cerr << '+' << bit[c].query(k, -1) << '\n';
				ans += bit[c].query(k, -1);
			}
			cout << ans << '\n';
		}
	}
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:204:8: warning: unused variable 'u' [-Wunused-variable]
  204 |    int u = a, v = b;
      |        ^
servers.cpp:204:15: warning: unused variable 'v' [-Wunused-variable]
  204 |    int u = a, v = b;
      |               ^
servers.cpp:205:16: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  205 |    pii l = no, r = no;
      |                ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13276 KB Output is correct
2 Correct 76 ms 16648 KB Output is correct
3 Correct 70 ms 16752 KB Output is correct
4 Correct 85 ms 16684 KB Output is correct
5 Correct 85 ms 16844 KB Output is correct
6 Correct 67 ms 16636 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13276 KB Output is correct
2 Correct 76 ms 16648 KB Output is correct
3 Correct 70 ms 16752 KB Output is correct
4 Correct 85 ms 16684 KB Output is correct
5 Correct 85 ms 16844 KB Output is correct
6 Correct 67 ms 16636 KB Output is correct
7 Incorrect 53 ms 14248 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 52 ms 13400 KB Output is correct
2 Correct 285 ms 73924 KB Output is correct
3 Correct 284 ms 74008 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13400 KB Output is correct
2 Correct 285 ms 73924 KB Output is correct
3 Correct 284 ms 74008 KB Output is correct
4 Incorrect 53 ms 14184 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 54 ms 13384 KB Output is correct
2 Correct 357 ms 81560 KB Output is correct
3 Correct 362 ms 81484 KB Output is correct
4 Correct 340 ms 94736 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13384 KB Output is correct
2 Correct 357 ms 81560 KB Output is correct
3 Correct 362 ms 81484 KB Output is correct
4 Correct 340 ms 94736 KB Output is correct
5 Incorrect 53 ms 14184 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 55 ms 13308 KB Output is correct
2 Correct 296 ms 82044 KB Output is correct
3 Correct 314 ms 73548 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13308 KB Output is correct
2 Correct 296 ms 82044 KB Output is correct
3 Correct 314 ms 73548 KB Output is correct
4 Incorrect 55 ms 14156 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 55 ms 13352 KB Output is correct
2 Correct 357 ms 81628 KB Output is correct
3 Correct 353 ms 81540 KB Output is correct
4 Correct 337 ms 94640 KB Output is correct
5 Correct 54 ms 14160 KB Output is correct
6 Correct 293 ms 82124 KB Output is correct
7 Correct 321 ms 73672 KB Output is correct
8 Correct 361 ms 74944 KB Output is correct
9 Correct 377 ms 75012 KB Output is correct
10 Correct 419 ms 82588 KB Output is correct
11 Correct 441 ms 81840 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13352 KB Output is correct
2 Correct 357 ms 81628 KB Output is correct
3 Correct 353 ms 81540 KB Output is correct
4 Correct 337 ms 94640 KB Output is correct
5 Correct 54 ms 14160 KB Output is correct
6 Correct 293 ms 82124 KB Output is correct
7 Correct 321 ms 73672 KB Output is correct
8 Correct 361 ms 74944 KB Output is correct
9 Correct 377 ms 75012 KB Output is correct
10 Correct 419 ms 82588 KB Output is correct
11 Correct 441 ms 81840 KB Output is correct
12 Incorrect 54 ms 14220 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 54 ms 13380 KB Output is correct
2 Correct 78 ms 16624 KB Output is correct
3 Correct 72 ms 16716 KB Output is correct
4 Correct 86 ms 16700 KB Output is correct
5 Correct 81 ms 16820 KB Output is correct
6 Correct 68 ms 16692 KB Output is correct
7 Correct 54 ms 14272 KB Output is correct
8 Correct 294 ms 74144 KB Output is correct
9 Correct 280 ms 73920 KB Output is correct
10 Correct 54 ms 14204 KB Output is correct
11 Correct 359 ms 81592 KB Output is correct
12 Correct 348 ms 81552 KB Output is correct
13 Correct 336 ms 94780 KB Output is correct
14 Correct 55 ms 14272 KB Output is correct
15 Correct 289 ms 82136 KB Output is correct
16 Correct 314 ms 73568 KB Output is correct
17 Correct 367 ms 74920 KB Output is correct
18 Correct 370 ms 75088 KB Output is correct
19 Correct 416 ms 82616 KB Output is correct
20 Correct 443 ms 82100 KB Output is correct
21 Correct 307 ms 73876 KB Output is correct
22 Correct 329 ms 74136 KB Output is correct
23 Correct 327 ms 74728 KB Output is correct
24 Correct 328 ms 74840 KB Output is correct
25 Correct 396 ms 76724 KB Output is correct
26 Correct 348 ms 73256 KB Output is correct
27 Correct 312 ms 73260 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13380 KB Output is correct
2 Correct 78 ms 16624 KB Output is correct
3 Correct 72 ms 16716 KB Output is correct
4 Correct 86 ms 16700 KB Output is correct
5 Correct 81 ms 16820 KB Output is correct
6 Correct 68 ms 16692 KB Output is correct
7 Correct 54 ms 14272 KB Output is correct
8 Correct 294 ms 74144 KB Output is correct
9 Correct 280 ms 73920 KB Output is correct
10 Correct 54 ms 14204 KB Output is correct
11 Correct 359 ms 81592 KB Output is correct
12 Correct 348 ms 81552 KB Output is correct
13 Correct 336 ms 94780 KB Output is correct
14 Correct 55 ms 14272 KB Output is correct
15 Correct 289 ms 82136 KB Output is correct
16 Correct 314 ms 73568 KB Output is correct
17 Correct 367 ms 74920 KB Output is correct
18 Correct 370 ms 75088 KB Output is correct
19 Correct 416 ms 82616 KB Output is correct
20 Correct 443 ms 82100 KB Output is correct
21 Correct 307 ms 73876 KB Output is correct
22 Correct 329 ms 74136 KB Output is correct
23 Correct 327 ms 74728 KB Output is correct
24 Correct 328 ms 74840 KB Output is correct
25 Correct 396 ms 76724 KB Output is correct
26 Correct 348 ms 73256 KB Output is correct
27 Correct 312 ms 73260 KB Output is correct
28 Incorrect 54 ms 14184 KB Extra information in the output file
29 Halted 0 ms 0 KB -