oj.uz

Submission #441769

# Submission time Handle Problem Language Result Execution time Memory
441769 2021-07-06T04:19:32 Z 8e7 Inside information (BOI21_servers) C++14
50 / 100
 448 ms 28368 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 35 ms 9592 KB Output is correct
2 Correct 48 ms 9860 KB Output is correct
3 Correct 44 ms 9836 KB Output is correct
4 Correct 50 ms 10048 KB Output is correct
5 Correct 49 ms 10308 KB Output is correct
6 Correct 45 ms 10080 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9592 KB Output is correct
2 Correct 48 ms 9860 KB Output is correct
3 Correct 44 ms 9836 KB Output is correct
4 Correct 50 ms 10048 KB Output is correct
5 Correct 49 ms 10308 KB Output is correct
6 Correct 45 ms 10080 KB Output is correct
7 Incorrect 35 ms 9400 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 42 ms 9636 KB Output is correct
2 Correct 212 ms 24092 KB Output is correct
3 Correct 218 ms 24108 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9636 KB Output is correct
2 Correct 212 ms 24092 KB Output is correct
3 Correct 218 ms 24108 KB Output is correct
4 Incorrect 34 ms 9412 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 9540 KB Output is correct
2 Correct 385 ms 27068 KB Output is correct
3 Correct 374 ms 27028 KB Output is correct
4 Correct 317 ms 28368 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9540 KB Output is correct
2 Correct 385 ms 27068 KB Output is correct
3 Correct 374 ms 27028 KB Output is correct
4 Correct 317 ms 28368 KB Output is correct
5 Incorrect 34 ms 9412 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 38 ms 9572 KB Output is correct
2 Correct 318 ms 19536 KB Output is correct
3 Correct 330 ms 18372 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9572 KB Output is correct
2 Correct 318 ms 19536 KB Output is correct
3 Correct 330 ms 18372 KB Output is correct
4 Incorrect 34 ms 9420 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 35 ms 9580 KB Output is correct
2 Correct 399 ms 26976 KB Output is correct
3 Correct 371 ms 27000 KB Output is correct
4 Correct 323 ms 28264 KB Output is correct
5 Correct 34 ms 9640 KB Output is correct
6 Correct 295 ms 19552 KB Output is correct
7 Correct 329 ms 18400 KB Output is correct
8 Correct 348 ms 19224 KB Output is correct
9 Correct 401 ms 19024 KB Output is correct
10 Correct 440 ms 23468 KB Output is correct
11 Correct 427 ms 22268 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9580 KB Output is correct
2 Correct 399 ms 26976 KB Output is correct
3 Correct 371 ms 27000 KB Output is correct
4 Correct 323 ms 28264 KB Output is correct
5 Correct 34 ms 9640 KB Output is correct
6 Correct 295 ms 19552 KB Output is correct
7 Correct 329 ms 18400 KB Output is correct
8 Correct 348 ms 19224 KB Output is correct
9 Correct 401 ms 19024 KB Output is correct
10 Correct 440 ms 23468 KB Output is correct
11 Correct 427 ms 22268 KB Output is correct
12 Incorrect 34 ms 9364 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 34 ms 9640 KB Output is correct
2 Correct 48 ms 9900 KB Output is correct
3 Correct 47 ms 9752 KB Output is correct
4 Correct 52 ms 10080 KB Output is correct
5 Correct 49 ms 10212 KB Output is correct
6 Correct 47 ms 9952 KB Output is correct
7 Correct 35 ms 9692 KB Output is correct
8 Correct 210 ms 24012 KB Output is correct
9 Correct 207 ms 24196 KB Output is correct
10 Correct 35 ms 9628 KB Output is correct
11 Correct 372 ms 27108 KB Output is correct
12 Correct 376 ms 27096 KB Output is correct
13 Correct 316 ms 28368 KB Output is correct
14 Correct 34 ms 9620 KB Output is correct
15 Correct 296 ms 19576 KB Output is correct
16 Correct 319 ms 18356 KB Output is correct
17 Correct 315 ms 19108 KB Output is correct
18 Correct 360 ms 19004 KB Output is correct
19 Correct 448 ms 23388 KB Output is correct
20 Correct 427 ms 22240 KB Output is correct
21 Correct 236 ms 25080 KB Output is correct
22 Correct 265 ms 23044 KB Output is correct
23 Correct 292 ms 19260 KB Output is correct
24 Correct 271 ms 19016 KB Output is correct
25 Correct 374 ms 26156 KB Output is correct
26 Correct 361 ms 17548 KB Output is correct
27 Correct 331 ms 18044 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9640 KB Output is correct
2 Correct 48 ms 9900 KB Output is correct
3 Correct 47 ms 9752 KB Output is correct
4 Correct 52 ms 10080 KB Output is correct
5 Correct 49 ms 10212 KB Output is correct
6 Correct 47 ms 9952 KB Output is correct
7 Correct 35 ms 9692 KB Output is correct
8 Correct 210 ms 24012 KB Output is correct
9 Correct 207 ms 24196 KB Output is correct
10 Correct 35 ms 9628 KB Output is correct
11 Correct 372 ms 27108 KB Output is correct
12 Correct 376 ms 27096 KB Output is correct
13 Correct 316 ms 28368 KB Output is correct
14 Correct 34 ms 9620 KB Output is correct
15 Correct 296 ms 19576 KB Output is correct
16 Correct 319 ms 18356 KB Output is correct
17 Correct 315 ms 19108 KB Output is correct
18 Correct 360 ms 19004 KB Output is correct
19 Correct 448 ms 23388 KB Output is correct
20 Correct 427 ms 22240 KB Output is correct
21 Correct 236 ms 25080 KB Output is correct
22 Correct 265 ms 23044 KB Output is correct
23 Correct 292 ms 19260 KB Output is correct
24 Correct 271 ms 19016 KB Output is correct
25 Correct 374 ms 26156 KB Output is correct
26 Correct 361 ms 17548 KB Output is correct
27 Correct 331 ms 18044 KB Output is correct
28 Incorrect 34 ms 9388 KB Extra information in the output file
29 Halted 0 ms 0 KB -