oj.uz

Submission #441763

# Submission time Handle Problem Language Result Execution time Memory
441763 2021-07-06T03:59:39 Z 8e7 Inside information (BOI21_servers) C++14
50 / 100
 491 ms 28492 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
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6

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 37 ms 9668 KB Output is correct
2 Correct 52 ms 9924 KB Output is correct
3 Correct 45 ms 9812 KB Output is correct
4 Correct 51 ms 10020 KB Output is correct
5 Correct 50 ms 10312 KB Output is correct
6 Correct 46 ms 9984 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9668 KB Output is correct
2 Correct 52 ms 9924 KB Output is correct
3 Correct 45 ms 9812 KB Output is correct
4 Correct 51 ms 10020 KB Output is correct
5 Correct 50 ms 10312 KB Output is correct
6 Correct 46 ms 9984 KB Output is correct
7 Incorrect 36 ms 9364 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 9596 KB Output is correct
2 Correct 207 ms 24048 KB Output is correct
3 Correct 208 ms 24056 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9596 KB Output is correct
2 Correct 207 ms 24048 KB Output is correct
3 Correct 208 ms 24056 KB Output is correct
4 Incorrect 35 ms 9556 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 36 ms 9560 KB Output is correct
2 Correct 405 ms 26976 KB Output is correct
3 Correct 421 ms 27100 KB Output is correct
4 Correct 321 ms 28236 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9560 KB Output is correct
2 Correct 405 ms 26976 KB Output is correct
3 Correct 421 ms 27100 KB Output is correct
4 Correct 321 ms 28236 KB Output is correct
5 Incorrect 34 ms 9360 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 37 ms 9548 KB Output is correct
2 Correct 330 ms 19580 KB Output is correct
3 Correct 383 ms 18432 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9548 KB Output is correct
2 Correct 330 ms 19580 KB Output is correct
3 Correct 383 ms 18432 KB Output is correct
4 Incorrect 35 ms 9380 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 9532 KB Output is correct
2 Correct 414 ms 26952 KB Output is correct
3 Correct 393 ms 27052 KB Output is correct
4 Correct 332 ms 28376 KB Output is correct
5 Correct 35 ms 9548 KB Output is correct
6 Correct 304 ms 19624 KB Output is correct
7 Correct 336 ms 18388 KB Output is correct
8 Correct 346 ms 19220 KB Output is correct
9 Correct 383 ms 19080 KB Output is correct
10 Correct 491 ms 23576 KB Output is correct
11 Correct 439 ms 22240 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9532 KB Output is correct
2 Correct 414 ms 26952 KB Output is correct
3 Correct 393 ms 27052 KB Output is correct
4 Correct 332 ms 28376 KB Output is correct
5 Correct 35 ms 9548 KB Output is correct
6 Correct 304 ms 19624 KB Output is correct
7 Correct 336 ms 18388 KB Output is correct
8 Correct 346 ms 19220 KB Output is correct
9 Correct 383 ms 19080 KB Output is correct
10 Correct 491 ms 23576 KB Output is correct
11 Correct 439 ms 22240 KB Output is correct
12 Incorrect 34 ms 9308 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 9708 KB Output is correct
2 Correct 50 ms 9968 KB Output is correct
3 Correct 46 ms 9800 KB Output is correct
4 Correct 50 ms 10004 KB Output is correct
5 Correct 54 ms 10256 KB Output is correct
6 Correct 48 ms 10044 KB Output is correct
7 Correct 35 ms 9664 KB Output is correct
8 Correct 218 ms 24124 KB Output is correct
9 Correct 209 ms 24016 KB Output is correct
10 Correct 34 ms 9592 KB Output is correct
11 Correct 402 ms 27108 KB Output is correct
12 Correct 383 ms 27000 KB Output is correct
13 Correct 317 ms 28492 KB Output is correct
14 Correct 35 ms 9584 KB Output is correct
15 Correct 307 ms 19560 KB Output is correct
16 Correct 329 ms 18280 KB Output is correct
17 Correct 331 ms 19208 KB Output is correct
18 Correct 390 ms 19120 KB Output is correct
19 Correct 473 ms 23564 KB Output is correct
20 Correct 457 ms 22192 KB Output is correct
21 Correct 239 ms 25200 KB Output is correct
22 Correct 248 ms 23084 KB Output is correct
23 Correct 293 ms 19224 KB Output is correct
24 Correct 288 ms 19028 KB Output is correct
25 Correct 377 ms 26176 KB Output is correct
26 Correct 343 ms 17568 KB Output is correct
27 Correct 332 ms 17784 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9708 KB Output is correct
2 Correct 50 ms 9968 KB Output is correct
3 Correct 46 ms 9800 KB Output is correct
4 Correct 50 ms 10004 KB Output is correct
5 Correct 54 ms 10256 KB Output is correct
6 Correct 48 ms 10044 KB Output is correct
7 Correct 35 ms 9664 KB Output is correct
8 Correct 218 ms 24124 KB Output is correct
9 Correct 209 ms 24016 KB Output is correct
10 Correct 34 ms 9592 KB Output is correct
11 Correct 402 ms 27108 KB Output is correct
12 Correct 383 ms 27000 KB Output is correct
13 Correct 317 ms 28492 KB Output is correct
14 Correct 35 ms 9584 KB Output is correct
15 Correct 307 ms 19560 KB Output is correct
16 Correct 329 ms 18280 KB Output is correct
17 Correct 331 ms 19208 KB Output is correct
18 Correct 390 ms 19120 KB Output is correct
19 Correct 473 ms 23564 KB Output is correct
20 Correct 457 ms 22192 KB Output is correct
21 Correct 239 ms 25200 KB Output is correct
22 Correct 248 ms 23084 KB Output is correct
23 Correct 293 ms 19224 KB Output is correct
24 Correct 288 ms 19028 KB Output is correct
25 Correct 377 ms 26176 KB Output is correct
26 Correct 343 ms 17568 KB Output is correct
27 Correct 332 ms 17784 KB Output is correct
28 Incorrect 35 ms 9384 KB Extra information in the output file
29 Halted 0 ms 0 KB -