oj.uz

Submission #441767

# Submission time Handle Problem Language Result Execution time Memory
441767 2021-07-06T04:13:32 Z 8e7 Inside information (BOI21_servers) C++14
50 / 100
 479 ms 28444 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << (*l) << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<pii> adj[maxn];
struct query{
	int ti, id, to;
	query() {ti = 0, id = 0, to = 0;}
	query(int x, int y, int z) {ti = x, id = y, to = z;}
};
vector<query> que[maxn];
int qtype[maxn], ans[maxn];

struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
int siz[maxn];
bool mark[maxn];
int found[maxn];

void dfs(int n, int par) {
	siz[n] = 1;
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			dfs(v.ff, n);
			siz[n] += siz[v.ff];
		}
	}
}
int get_centroid(int n, int par, int tot) {
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			if (2 * siz[v.ff] >= tot) return get_centroid(v.ff, n, tot);
		}
	}	
	return n;
}

void get_node(int n, int par, int w, vector<pii> & ret, int dir) {
	ret.push_back({n, w});
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff] && (dir == 2 ? true : (dir ? v.ss > w : v.ss < w))) {
			get_node(v.ff, n, v.ss, ret, dir);
		}
	}
}
void recur(int n, int par, vector<int> & ret) {
	ret.push_back(n);
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			recur(v.ff, n, ret);
		}
	}
}
void solve(vector<int> a) {
	//debug(49);
	//pary(a.begin(), a.end());
	for (int i:a) mark[i] = 1;
	dfs(a[0], 0);	
	vector<pii> op;
	int cent = get_centroid(a[0], 0, a.size());
	//debug(cent);
	sort(adj[cent].begin(), adj[cent].end(), [&](pii x, pii y) {return x.ss > y.ss;});	
	for (auto v:adj[cent]) {
		if (!mark[v.ff]) continue;
		vector<pii> se;
		get_node(v.ff, cent, v.ss, se, 0);
		for (auto node:se) {
			//debug(7122, node.ff);
			for (auto q:que[node.ff]) {
				if (q.to == 0) {
					ans[q.id] += bit.query(q.ti) + 1;	
				} else if (mark[q.to]) {
					if (q.to != cent) ans[q.id] = (found[q.to] && found[q.to] <= q.ti);	
					else ans[q.id] = v.ss <= q.ti;
				}
			}
		}
		se.clear();
		get_node(v.ff, cent, v.ss, se, 1);
		for (auto node:se) {
			//debug(2217, node.ff);
			found[node.ff] = node.ss;
			bit.modify(node.ss, 1);
		}
		op.insert(op.end(), se.begin(), se.end());
	}
	for (auto q:que[cent]) {
		if (q.to == 0) ans[q.id] += 1 + bit.query(q.ti);
		else if (mark[q.to]){
			if (q.to == cent) ans[q.id] = 1;
			else ans[q.id] = found[q.to] && found[q.to] <= q.ti;
		}
	}
	for (auto i:op) {
		found[i.ff] = 0;
		bit.modify(i.ss, -1);
	}
	vector<vector<int> > rec;
	for (auto v:adj[cent]) {
		if (!mark[v.ff]) continue;
		vector<int> add;
		recur(v.ff, cent, add);
		rec.push_back(add);	
	}
	for (int i:a) mark[i] = 0;
	for (auto i:rec) solve(i);
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	int cur = 1, qcnt = 0;
	for (int i = 0;i < n + k - 1;i++) {
		char type;
		cin >> type;
		if (type == 'S') {
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cur});
			adj[b].push_back({a, cur});
			cur++;
		} else if (type == 'Q') {
			int a, b;
			cin >> a >> b;
			qtype[qcnt] = 0;
			que[b].push_back(query(cur - 1, qcnt++, a));
		} else {
			int d;
			cin >> d;
			qtype[qcnt] = 1;
			que[d].push_back(query(cur - 1, qcnt++, 0));
		}
	}
	vector<int> st;
	for (int i = 1;i <= n;i++) st.push_back(i);
	solve(st);
	for (int i = 0;i < k;i++) {
		if (qtype[i]) cout << ans[i] << "\n";
		else cout << (ans[i] ? "yes" : "no") << "\n";
	}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
C 3
Q 5 1
C 6
Q 1 5
C 1
C 2
C 4
C 5

7 7
S 4 5
S 2 3
S 5 6
S 6 7
S 3 4
S 1 2
C 1
C 2
C 3
C 4
C 5
C 6
C 7
   */

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9668 KB Output is correct
2 Correct 48 ms 9860 KB Output is correct
3 Correct 44 ms 9724 KB Output is correct
4 Correct 49 ms 10048 KB Output is correct
5 Correct 50 ms 10392 KB Output is correct
6 Correct 46 ms 9960 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9668 KB Output is correct
2 Correct 48 ms 9860 KB Output is correct
3 Correct 44 ms 9724 KB Output is correct
4 Correct 49 ms 10048 KB Output is correct
5 Correct 50 ms 10392 KB Output is correct
6 Correct 46 ms 9960 KB Output is correct
7 Incorrect 34 ms 9416 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 35 ms 9688 KB Output is correct
2 Correct 220 ms 24108 KB Output is correct
3 Correct 203 ms 24072 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9688 KB Output is correct
2 Correct 220 ms 24108 KB Output is correct
3 Correct 203 ms 24072 KB Output is correct
4 Incorrect 34 ms 9368 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 34 ms 9644 KB Output is correct
2 Correct 424 ms 26988 KB Output is correct
3 Correct 406 ms 26980 KB Output is correct
4 Correct 332 ms 28236 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9644 KB Output is correct
2 Correct 424 ms 26988 KB Output is correct
3 Correct 406 ms 26980 KB Output is correct
4 Correct 332 ms 28236 KB Output is correct
5 Incorrect 33 ms 9324 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 34 ms 9564 KB Output is correct
2 Correct 302 ms 19496 KB Output is correct
3 Correct 320 ms 18272 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9564 KB Output is correct
2 Correct 302 ms 19496 KB Output is correct
3 Correct 320 ms 18272 KB Output is correct
4 Incorrect 34 ms 9332 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 34 ms 9540 KB Output is correct
2 Correct 390 ms 27020 KB Output is correct
3 Correct 390 ms 26980 KB Output is correct
4 Correct 330 ms 28444 KB Output is correct
5 Correct 34 ms 9520 KB Output is correct
6 Correct 297 ms 19504 KB Output is correct
7 Correct 314 ms 18284 KB Output is correct
8 Correct 309 ms 19164 KB Output is correct
9 Correct 348 ms 18928 KB Output is correct
10 Correct 440 ms 23444 KB Output is correct
11 Correct 467 ms 22192 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9540 KB Output is correct
2 Correct 390 ms 27020 KB Output is correct
3 Correct 390 ms 26980 KB Output is correct
4 Correct 330 ms 28444 KB Output is correct
5 Correct 34 ms 9520 KB Output is correct
6 Correct 297 ms 19504 KB Output is correct
7 Correct 314 ms 18284 KB Output is correct
8 Correct 309 ms 19164 KB Output is correct
9 Correct 348 ms 18928 KB Output is correct
10 Correct 440 ms 23444 KB Output is correct
11 Correct 467 ms 22192 KB Output is correct
12 Incorrect 36 ms 9396 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 35 ms 9612 KB Output is correct
2 Correct 52 ms 9908 KB Output is correct
3 Correct 47 ms 9760 KB Output is correct
4 Correct 52 ms 10052 KB Output is correct
5 Correct 53 ms 10304 KB Output is correct
6 Correct 45 ms 9984 KB Output is correct
7 Correct 34 ms 9668 KB Output is correct
8 Correct 198 ms 24076 KB Output is correct
9 Correct 213 ms 24052 KB Output is correct
10 Correct 34 ms 9628 KB Output is correct
11 Correct 385 ms 26984 KB Output is correct
12 Correct 430 ms 26944 KB Output is correct
13 Correct 326 ms 28240 KB Output is correct
14 Correct 34 ms 9544 KB Output is correct
15 Correct 304 ms 19560 KB Output is correct
16 Correct 320 ms 18272 KB Output is correct
17 Correct 329 ms 19388 KB Output is correct
18 Correct 376 ms 18956 KB Output is correct
19 Correct 479 ms 23584 KB Output is correct
20 Correct 417 ms 22160 KB Output is correct
21 Correct 243 ms 25164 KB Output is correct
22 Correct 243 ms 23060 KB Output is correct
23 Correct 281 ms 19188 KB Output is correct
24 Correct 279 ms 19028 KB Output is correct
25 Correct 401 ms 26176 KB Output is correct
26 Correct 346 ms 17560 KB Output is correct
27 Correct 342 ms 17804 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9612 KB Output is correct
2 Correct 52 ms 9908 KB Output is correct
3 Correct 47 ms 9760 KB Output is correct
4 Correct 52 ms 10052 KB Output is correct
5 Correct 53 ms 10304 KB Output is correct
6 Correct 45 ms 9984 KB Output is correct
7 Correct 34 ms 9668 KB Output is correct
8 Correct 198 ms 24076 KB Output is correct
9 Correct 213 ms 24052 KB Output is correct
10 Correct 34 ms 9628 KB Output is correct
11 Correct 385 ms 26984 KB Output is correct
12 Correct 430 ms 26944 KB Output is correct
13 Correct 326 ms 28240 KB Output is correct
14 Correct 34 ms 9544 KB Output is correct
15 Correct 304 ms 19560 KB Output is correct
16 Correct 320 ms 18272 KB Output is correct
17 Correct 329 ms 19388 KB Output is correct
18 Correct 376 ms 18956 KB Output is correct
19 Correct 479 ms 23584 KB Output is correct
20 Correct 417 ms 22160 KB Output is correct
21 Correct 243 ms 25164 KB Output is correct
22 Correct 243 ms 23060 KB Output is correct
23 Correct 281 ms 19188 KB Output is correct
24 Correct 279 ms 19028 KB Output is correct
25 Correct 401 ms 26176 KB Output is correct
26 Correct 346 ms 17560 KB Output is correct
27 Correct 342 ms 17804 KB Output is correct
28 Incorrect 35 ms 9420 KB Extra information in the output file
29 Halted 0 ms 0 KB -