oj.uz

Submission #771934

# Submission time Handle Problem Language Result Execution time Memory
771934 2023-07-03T12:22:56 Z LittleCube Inside information (BOI21_servers) C++17
52.5 / 100
 450 ms 91648 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 || path.S > t)
					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 56 ms 13332 KB Output is correct
2 Correct 76 ms 15180 KB Output is correct
3 Correct 69 ms 15436 KB Output is correct
4 Correct 87 ms 15308 KB Output is correct
5 Correct 83 ms 15436 KB Output is correct
6 Correct 68 ms 15236 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13332 KB Output is correct
2 Correct 76 ms 15180 KB Output is correct
3 Correct 69 ms 15436 KB Output is correct
4 Correct 87 ms 15308 KB Output is correct
5 Correct 83 ms 15436 KB Output is correct
6 Correct 68 ms 15236 KB Output is correct
7 Incorrect 54 ms 13368 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 56 ms 13344 KB Output is correct
2 Correct 277 ms 71096 KB Output is correct
3 Correct 278 ms 71076 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13344 KB Output is correct
2 Correct 277 ms 71096 KB Output is correct
3 Correct 278 ms 71076 KB Output is correct
4 Correct 53 ms 13376 KB Output is correct
5 Correct 279 ms 73804 KB Output is correct
6 Correct 227 ms 73088 KB Output is correct
7 Correct 244 ms 73176 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13328 KB Output is correct
2 Correct 344 ms 78492 KB Output is correct
3 Correct 342 ms 78424 KB Output is correct
4 Correct 321 ms 91600 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13328 KB Output is correct
2 Correct 344 ms 78492 KB Output is correct
3 Correct 342 ms 78424 KB Output is correct
4 Correct 321 ms 91600 KB Output is correct
5 Incorrect 59 ms 13348 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 13388 KB Output is correct
2 Correct 303 ms 79064 KB Output is correct
3 Correct 312 ms 70628 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13388 KB Output is correct
2 Correct 303 ms 79064 KB Output is correct
3 Correct 312 ms 70628 KB Output is correct
4 Incorrect 55 ms 13344 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 13388 KB Output is correct
2 Correct 349 ms 78480 KB Output is correct
3 Correct 336 ms 78496 KB Output is correct
4 Correct 327 ms 91648 KB Output is correct
5 Correct 55 ms 13284 KB Output is correct
6 Correct 283 ms 79008 KB Output is correct
7 Correct 297 ms 70396 KB Output is correct
8 Correct 358 ms 71864 KB Output is correct
9 Correct 357 ms 71848 KB Output is correct
10 Correct 408 ms 79564 KB Output is correct
11 Correct 448 ms 79120 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13388 KB Output is correct
2 Correct 349 ms 78480 KB Output is correct
3 Correct 336 ms 78496 KB Output is correct
4 Correct 327 ms 91648 KB Output is correct
5 Correct 55 ms 13284 KB Output is correct
6 Correct 283 ms 79008 KB Output is correct
7 Correct 297 ms 70396 KB Output is correct
8 Correct 358 ms 71864 KB Output is correct
9 Correct 357 ms 71848 KB Output is correct
10 Correct 408 ms 79564 KB Output is correct
11 Correct 448 ms 79120 KB Output is correct
12 Incorrect 54 ms 13388 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 56 ms 13308 KB Output is correct
2 Correct 77 ms 15156 KB Output is correct
3 Correct 73 ms 15308 KB Output is correct
4 Correct 85 ms 15356 KB Output is correct
5 Correct 81 ms 15480 KB Output is correct
6 Correct 68 ms 15304 KB Output is correct
7 Correct 53 ms 13392 KB Output is correct
8 Correct 273 ms 71160 KB Output is correct
9 Correct 298 ms 71092 KB Output is correct
10 Correct 55 ms 13344 KB Output is correct
11 Correct 346 ms 78456 KB Output is correct
12 Correct 334 ms 78420 KB Output is correct
13 Correct 324 ms 91552 KB Output is correct
14 Correct 62 ms 13436 KB Output is correct
15 Correct 291 ms 79060 KB Output is correct
16 Correct 302 ms 70476 KB Output is correct
17 Correct 371 ms 71876 KB Output is correct
18 Correct 355 ms 71884 KB Output is correct
19 Correct 417 ms 79644 KB Output is correct
20 Correct 450 ms 78800 KB Output is correct
21 Correct 304 ms 70852 KB Output is correct
22 Correct 305 ms 70784 KB Output is correct
23 Correct 345 ms 71784 KB Output is correct
24 Correct 326 ms 71700 KB Output is correct
25 Correct 391 ms 73564 KB Output is correct
26 Correct 336 ms 70188 KB Output is correct
27 Correct 316 ms 70224 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13308 KB Output is correct
2 Correct 77 ms 15156 KB Output is correct
3 Correct 73 ms 15308 KB Output is correct
4 Correct 85 ms 15356 KB Output is correct
5 Correct 81 ms 15480 KB Output is correct
6 Correct 68 ms 15304 KB Output is correct
7 Correct 53 ms 13392 KB Output is correct
8 Correct 273 ms 71160 KB Output is correct
9 Correct 298 ms 71092 KB Output is correct
10 Correct 55 ms 13344 KB Output is correct
11 Correct 346 ms 78456 KB Output is correct
12 Correct 334 ms 78420 KB Output is correct
13 Correct 324 ms 91552 KB Output is correct
14 Correct 62 ms 13436 KB Output is correct
15 Correct 291 ms 79060 KB Output is correct
16 Correct 302 ms 70476 KB Output is correct
17 Correct 371 ms 71876 KB Output is correct
18 Correct 355 ms 71884 KB Output is correct
19 Correct 417 ms 79644 KB Output is correct
20 Correct 450 ms 78800 KB Output is correct
21 Correct 304 ms 70852 KB Output is correct
22 Correct 305 ms 70784 KB Output is correct
23 Correct 345 ms 71784 KB Output is correct
24 Correct 326 ms 71700 KB Output is correct
25 Correct 391 ms 73564 KB Output is correct
26 Correct 336 ms 70188 KB Output is correct
27 Correct 316 ms 70224 KB Output is correct
28 Incorrect 55 ms 13284 KB Extra information in the output file
29 Halted 0 ms 0 KB -