oj.uz

Submission #924195

# Submission time Handle Problem Language Result Execution time Memory
924195 2024-02-08T16:06:30 Z 42kangaroo Inside information (BOI21_servers) C++17
50 / 100
 234 ms 66644 KB 
//
// Created by 42kangaroo on 07/02/2024.
//
#include "bits/stdc++.h"

using namespace std;

template<typename T>
using g_t = vector<vector<T>>;

struct Que {
	char c;
	int f, s;
	string an;
};

struct BinL {
	bool asc, desc;
	int p, upVal, downVal;
};

struct Ed {
	int a, b, w;
};

array<int, 120005> logT;
g_t<BinL> binL;
g_t<Ed> g;
vector<int> de;

void dfs(int n, int p, int d, vector<pair<int, int>> &pa) {
	pa[n].first = p;
	de[n] = d;
	for (auto &e: g[n]) {
		if (e.b == p) {
			pa[n].second = e.w;
			continue;
		}
		dfs(e.b, n, d + 1, pa);
	}
}

BinL combine(const BinL &l, const BinL &r) {
	BinL res{};
	res.p = r.p;
	res.upVal = r.upVal;
	res.downVal = l.downVal;
	res.asc = l.asc && r.asc && l.upVal > r.downVal;
	res.desc = l.desc && r.desc && l.upVal < r.downVal;
	return res;
}

void binLPrep(vector<pair<int, int>> &p) {
	binL = g_t<BinL>(logT[p.size()] + 1, vector<BinL>(p.size()));
	for (int i = 0; i < p.size(); ++i) {
		binL[0][i] = {true, true, p[i].first, p[i].second, p[i].second};
	}
	for (int i = 1; i < binL.size(); ++i) {
		for (int j = 0; j < p.size(); ++j) {
			binL[i][j] = combine(binL[i - 1][j], binL[i - 1][binL[i - 1][j].p]);
		}
	}
}

bool connected(int i, int st, int en) {
	if (st == en) return true;
	bool sw = false;
	if (de[st] < de[en]) {
		sw = true;
		swap(st, en);
	}
	int k = de[st] - de[en];
	BinL biSt{true, true, -1, -1, -1};
	BinL biEn{true, true, -1, -1, -1};
	for (int j = 0; k; k >>= 1, ++j) {
		if (k & 1) {
			if (biSt.p == -1) {
				biSt = binL[j][st];
			} else {
				biSt = combine(biSt, binL[j][st]);
			}
			st = biSt.p;
		}
	}
	if (st == en) {
		if (sw) {
			return biSt.asc && biSt.downVal <= i;
		} else {
			return biSt.desc && biSt.upVal <= i;
		}
	}

	for (int j = binL.size() - 1; j >= 0; j--) {
		if (binL[j][st].p != binL[j][en].p) {
			if (biSt.p == -1) {
				biSt = binL[j][st];
			} else {
				biSt = combine(biSt, binL[j][st]);
			}
			st = biSt.p;
			if (biEn.p == -1) {
				biEn = binL[j][en];
			} else {
				biEn = combine(biEn, binL[j][en]);
			}
			en = biEn.p;
		}
	}
	if (biSt.p == -1) {
		biSt = binL[0][st];
	} else {
		biSt = combine(biSt, binL[0][st]);
	}
	if (biEn.p == -1) {
		biEn = binL[0][en];
	} else {
		biEn = combine(biEn, binL[0][en]);
	}
	if (sw) {
		swap(biEn, biSt);
	}
	return biSt.desc && biEn.asc && biSt.upVal < biEn.upVal && biEn.downVal <= i;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	logT[1] = 0;
	for (int i = 2; i < logT.size(); ++i) {
		logT[i] = logT[i / 2] + 1;
	}
	g = g_t<Ed>(n);
	vector<Que> que(k + n - 1);
	for (int i = 0; i < k + n - 1; ++i) {
		char c;
		cin >> c;
		if (c == 'S') {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			g[a].push_back({a, b, i});
			g[b].push_back({b, a, i});
			que[i] = {c, a, b, ""};
		}
		if (c == 'Q') {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			que[i] = {c, a, b, ""};
		}
		if (c == 'C') {
			int a;
			cin >> a;
			--a;
			que[i] = {c, a, -1, ""};
		}
	}
	vector<pair<int, int>> p(n, {0, 0});
	de = vector<int>(n);
	dfs(0, 0, 0, p);
	binLPrep(p);
	for (int i = 0; i < que.size(); ++i) {
		if (que[i].c == 'Q') {
			que[i].an = (connected(i, que[i].s, que[i].f) ? "yes" : "no");
		}
	}
	for (int i = 0; i < que.size(); ++i) {
		if (que[i].an != "") cout << que[i].an << "\n";
	}
}

Compilation message

servers.cpp: In function 'void binLPrep(std::vector<std::pair<int, int> >&)':
servers.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < p.size(); ++i) {
      |                  ~~^~~~~~~~~~
servers.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<BinL, std::allocator<BinL> >, std::allocator<std::vector<BinL, std::allocator<BinL> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 1; i < binL.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int j = 0; j < p.size(); ++j) {
      |                   ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 120005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for (int i = 2; i < logT.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |  for (int i = 0; i < que.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
servers.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for (int i = 0; i < que.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6736 KB Output is correct
2 Correct 37 ms 8180 KB Output is correct
3 Correct 28 ms 8272 KB Output is correct
4 Correct 42 ms 8276 KB Output is correct
5 Correct 35 ms 8276 KB Output is correct
6 Correct 28 ms 8140 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6736 KB Output is correct
2 Correct 37 ms 8180 KB Output is correct
3 Correct 28 ms 8272 KB Output is correct
4 Correct 42 ms 8276 KB Output is correct
5 Correct 35 ms 8276 KB Output is correct
6 Correct 28 ms 8140 KB Output is correct
7 Incorrect 22 ms 6744 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 23 ms 6744 KB Output is correct
2 Correct 131 ms 55304 KB Output is correct
3 Correct 134 ms 58060 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6744 KB Output is correct
2 Correct 131 ms 55304 KB Output is correct
3 Correct 134 ms 58060 KB Output is correct
4 Incorrect 21 ms 7772 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 22 ms 6748 KB Output is correct
2 Correct 100 ms 63312 KB Output is correct
3 Correct 103 ms 66584 KB Output is correct
4 Correct 154 ms 66472 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6748 KB Output is correct
2 Correct 100 ms 63312 KB Output is correct
3 Correct 103 ms 66584 KB Output is correct
4 Correct 154 ms 66472 KB Output is correct
5 Incorrect 21 ms 7772 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 23 ms 6820 KB Output is correct
2 Correct 127 ms 55736 KB Output is correct
3 Correct 110 ms 59472 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6820 KB Output is correct
2 Correct 127 ms 55736 KB Output is correct
3 Correct 110 ms 59472 KB Output is correct
4 Incorrect 23 ms 7760 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 22 ms 6840 KB Output is correct
2 Correct 111 ms 63316 KB Output is correct
3 Correct 96 ms 66644 KB Output is correct
4 Correct 152 ms 66532 KB Output is correct
5 Correct 23 ms 8016 KB Output is correct
6 Correct 128 ms 58948 KB Output is correct
7 Correct 100 ms 59372 KB Output is correct
8 Correct 208 ms 59988 KB Output is correct
9 Correct 142 ms 59912 KB Output is correct
10 Correct 137 ms 64428 KB Output is correct
11 Correct 234 ms 63756 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6840 KB Output is correct
2 Correct 111 ms 63316 KB Output is correct
3 Correct 96 ms 66644 KB Output is correct
4 Correct 152 ms 66532 KB Output is correct
5 Correct 23 ms 8016 KB Output is correct
6 Correct 128 ms 58948 KB Output is correct
7 Correct 100 ms 59372 KB Output is correct
8 Correct 208 ms 59988 KB Output is correct
9 Correct 142 ms 59912 KB Output is correct
10 Correct 137 ms 64428 KB Output is correct
11 Correct 234 ms 63756 KB Output is correct
12 Incorrect 24 ms 7716 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 25 ms 6832 KB Output is correct
2 Correct 45 ms 8020 KB Output is correct
3 Correct 29 ms 8284 KB Output is correct
4 Correct 41 ms 8264 KB Output is correct
5 Correct 34 ms 8404 KB Output is correct
6 Correct 28 ms 8284 KB Output is correct
7 Correct 21 ms 6748 KB Output is correct
8 Correct 131 ms 55340 KB Output is correct
9 Correct 124 ms 58116 KB Output is correct
10 Correct 21 ms 7772 KB Output is correct
11 Correct 98 ms 66644 KB Output is correct
12 Correct 97 ms 66572 KB Output is correct
13 Correct 137 ms 66528 KB Output is correct
14 Correct 23 ms 7760 KB Output is correct
15 Correct 114 ms 58960 KB Output is correct
16 Correct 102 ms 59540 KB Output is correct
17 Correct 155 ms 59988 KB Output is correct
18 Correct 121 ms 59988 KB Output is correct
19 Correct 135 ms 64512 KB Output is correct
20 Correct 192 ms 63928 KB Output is correct
21 Correct 124 ms 58560 KB Output is correct
22 Correct 119 ms 58748 KB Output is correct
23 Correct 122 ms 59216 KB Output is correct
24 Correct 123 ms 59272 KB Output is correct
25 Correct 112 ms 60672 KB Output is correct
26 Correct 91 ms 58660 KB Output is correct
27 Correct 98 ms 58728 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6832 KB Output is correct
2 Correct 45 ms 8020 KB Output is correct
3 Correct 29 ms 8284 KB Output is correct
4 Correct 41 ms 8264 KB Output is correct
5 Correct 34 ms 8404 KB Output is correct
6 Correct 28 ms 8284 KB Output is correct
7 Correct 21 ms 6748 KB Output is correct
8 Correct 131 ms 55340 KB Output is correct
9 Correct 124 ms 58116 KB Output is correct
10 Correct 21 ms 7772 KB Output is correct
11 Correct 98 ms 66644 KB Output is correct
12 Correct 97 ms 66572 KB Output is correct
13 Correct 137 ms 66528 KB Output is correct
14 Correct 23 ms 7760 KB Output is correct
15 Correct 114 ms 58960 KB Output is correct
16 Correct 102 ms 59540 KB Output is correct
17 Correct 155 ms 59988 KB Output is correct
18 Correct 121 ms 59988 KB Output is correct
19 Correct 135 ms 64512 KB Output is correct
20 Correct 192 ms 63928 KB Output is correct
21 Correct 124 ms 58560 KB Output is correct
22 Correct 119 ms 58748 KB Output is correct
23 Correct 122 ms 59216 KB Output is correct
24 Correct 123 ms 59272 KB Output is correct
25 Correct 112 ms 60672 KB Output is correct
26 Correct 91 ms 58660 KB Output is correct
27 Correct 98 ms 58728 KB Output is correct
28 Incorrect 22 ms 7772 KB Extra information in the output file
29 Halted 0 ms 0 KB -