Submission #938248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938248	2024-03-05T03:37:50 Z	Gromp15	Inside information (BOI21_servers)	C++17	5 / 100	3500 ms	11896 KB

servers

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9;
void test_case() {
	int n, q;
	cin >> n >> q;
	vector<vector<ar<int, 2>>> adj(n+1);
	vector<ar<int, 5>> queries;
	vector<int> ans(q);
	vector<bool> type(q);
	for (int i = 0, qidx = 0; i < n + q - 1; i++) {
		char c; cin >> c;
		int x, y;
		cin >> x;
		if (c != 'C') cin >> y;
		if (c == 'S') {
			adj[x].push_back({y, i});
			adj[y].push_back({x, i});
		}
		else {
			if (c == 'Q') {
				queries.push_back({0, x, y, qidx++, i});
			}
			else {
				queries.push_back({1, x, -1, qidx++, i});
			}
		}
	}
	for (auto [tp, x, y, ans_idx, time] : queries) {
		if (tp == 0) {
			vector<int> dist(n+1, -1);
			dist[x] = time;
			auto dfs = [&](auto&& s, int v) -> void {
				for (auto [u, w] : adj[v]) if (dist[v] >= w && ckmax(dist[u], w)) {
					s(s, u);
				}
			};
			dfs(dfs, x);
			type[ans_idx] = 1;
			ans[ans_idx] = bool(~dist[y]); // good if it's not -1
		}
		else {
			vector<int> dist(n+1, INF);
			dist[x] = -1;
			auto dfs = [&](auto&& s, int v) -> void {
				for (auto [u, w] : adj[v]) if (dist[v] <= w && ckmin(dist[u], w)) {
					s(s, u);
				}
			};
			dfs(dfs, x);
			int cnt = 0;
			for (int i = 1; i <= n; i++) {
				cnt += dist[i] <= time;
			}
			ans[ans_idx] = cnt;
		}
	}
	for (int i = 0; i < q; i++) {
		if (type[i]) {
			cout << (ans[i] ? "yes":"no") << '\n';
		}
		else cout << ans[i] << '\n';
	}




}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

Subtask #1
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3536 KB	Output is correct
2	Correct	51 ms	3788 KB	Output is correct
3	Correct	236 ms	3884 KB	Output is correct
4	Correct	48 ms	3780 KB	Output is correct
5	Correct	48 ms	3824 KB	Output is correct
6	Correct	1059 ms	3812 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3536 KB	Output is correct
2	Correct	51 ms	3788 KB	Output is correct
3	Correct	236 ms	3884 KB	Output is correct
4	Correct	48 ms	3780 KB	Output is correct
5	Correct	48 ms	3824 KB	Output is correct
6	Correct	1059 ms	3812 KB	Output is correct
7	Correct	22 ms	3776 KB	Output is correct
8	Correct	270 ms	5332 KB	Output is correct
9	Correct	605 ms	4968 KB	Output is correct
10	Correct	261 ms	5596 KB	Output is correct
11	Correct	258 ms	5616 KB	Output is correct
12	Correct	1531 ms	4920 KB	Output is correct

Subtask #3
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	3780 KB	Output is correct
2	Execution timed out	3545 ms	11096 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	3780 KB	Output is correct
2	Execution timed out	3545 ms	11096 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3660 KB	Output is correct
2	Correct	767 ms	10596 KB	Output is correct
3	Correct	803 ms	10804 KB	Output is correct
4	Execution timed out	3511 ms	11588 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3660 KB	Output is correct
2	Correct	767 ms	10596 KB	Output is correct
3	Correct	803 ms	10804 KB	Output is correct
4	Execution timed out	3511 ms	11588 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3688 KB	Output is correct
2	Execution timed out	3534 ms	11236 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3688 KB	Output is correct
2	Execution timed out	3534 ms	11236 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3788 KB	Output is correct
2	Correct	771 ms	10720 KB	Output is correct
3	Correct	748 ms	10596 KB	Output is correct
4	Execution timed out	3546 ms	11896 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3788 KB	Output is correct
2	Correct	771 ms	10720 KB	Output is correct
3	Correct	748 ms	10596 KB	Output is correct
4	Execution timed out	3546 ms	11896 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3780 KB	Output is correct
2	Correct	51 ms	3892 KB	Output is correct
3	Correct	239 ms	5076 KB	Output is correct
4	Correct	48 ms	4564 KB	Output is correct
5	Correct	48 ms	3868 KB	Output is correct
6	Correct	1045 ms	4832 KB	Output is correct
7	Correct	26 ms	3788 KB	Output is correct
8	Execution timed out	3536 ms	11060 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3780 KB	Output is correct
2	Correct	51 ms	3892 KB	Output is correct
3	Correct	239 ms	5076 KB	Output is correct
4	Correct	48 ms	4564 KB	Output is correct
5	Correct	48 ms	3868 KB	Output is correct
6	Correct	1045 ms	4832 KB	Output is correct
7	Correct	26 ms	3788 KB	Output is correct
8	Execution timed out	3536 ms	11060 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #938248

Compilation message