oj.uz

Submission #441762

# Submission time Handle Problem Language Result Execution time Memory
441762 2021-07-06T03:58:07 Z 8e7 Inside information (BOI21_servers) C++14
50 / 100
 485 ms 31104 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;});	
	int con = 1;
	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);
		con += se.size();
		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] += con;
		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 39 ms 9636 KB Output is correct
2 Correct 50 ms 11288 KB Output is correct
3 Correct 56 ms 11204 KB Output is correct
4 Correct 51 ms 11432 KB Output is correct
5 Correct 51 ms 11716 KB Output is correct
6 Correct 46 ms 11428 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9636 KB Output is correct
2 Correct 50 ms 11288 KB Output is correct
3 Correct 56 ms 11204 KB Output is correct
4 Correct 51 ms 11432 KB Output is correct
5 Correct 51 ms 11716 KB Output is correct
6 Correct 46 ms 11428 KB Output is correct
7 Incorrect 41 ms 10276 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 38 ms 9712 KB Output is correct
2 Correct 225 ms 26928 KB Output is correct
3 Correct 219 ms 26912 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9712 KB Output is correct
2 Correct 225 ms 26928 KB Output is correct
3 Correct 219 ms 26912 KB Output is correct
4 Incorrect 35 ms 10256 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 9564 KB Output is correct
2 Correct 431 ms 29524 KB Output is correct
3 Correct 391 ms 29664 KB Output is correct
4 Correct 342 ms 30800 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9564 KB Output is correct
2 Correct 431 ms 29524 KB Output is correct
3 Correct 391 ms 29664 KB Output is correct
4 Correct 342 ms 30800 KB Output is correct
5 Incorrect 36 ms 10208 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 9552 KB Output is correct
2 Correct 318 ms 22348 KB Output is correct
3 Correct 325 ms 21096 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9552 KB Output is correct
2 Correct 318 ms 22348 KB Output is correct
3 Correct 325 ms 21096 KB Output is correct
4 Incorrect 40 ms 10180 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 36 ms 9524 KB Output is correct
2 Correct 441 ms 29616 KB Output is correct
3 Correct 385 ms 29600 KB Output is correct
4 Correct 317 ms 30808 KB Output is correct
5 Correct 36 ms 10596 KB Output is correct
6 Correct 319 ms 22404 KB Output is correct
7 Correct 382 ms 21108 KB Output is correct
8 Correct 329 ms 22060 KB Output is correct
9 Correct 376 ms 21828 KB Output is correct
10 Correct 475 ms 26252 KB Output is correct
11 Correct 436 ms 25056 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9524 KB Output is correct
2 Correct 441 ms 29616 KB Output is correct
3 Correct 385 ms 29600 KB Output is correct
4 Correct 317 ms 30808 KB Output is correct
5 Correct 36 ms 10596 KB Output is correct
6 Correct 319 ms 22404 KB Output is correct
7 Correct 382 ms 21108 KB Output is correct
8 Correct 329 ms 22060 KB Output is correct
9 Correct 376 ms 21828 KB Output is correct
10 Correct 475 ms 26252 KB Output is correct
11 Correct 436 ms 25056 KB Output is correct
12 Incorrect 39 ms 10196 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 36 ms 9676 KB Output is correct
2 Correct 53 ms 11240 KB Output is correct
3 Correct 46 ms 11208 KB Output is correct
4 Correct 60 ms 11460 KB Output is correct
5 Correct 54 ms 11672 KB Output is correct
6 Correct 48 ms 11364 KB Output is correct
7 Correct 38 ms 10564 KB Output is correct
8 Correct 240 ms 26880 KB Output is correct
9 Correct 258 ms 26964 KB Output is correct
10 Correct 35 ms 10512 KB Output is correct
11 Correct 373 ms 29796 KB Output is correct
12 Correct 404 ms 29988 KB Output is correct
13 Correct 324 ms 31104 KB Output is correct
14 Correct 34 ms 10440 KB Output is correct
15 Correct 299 ms 22372 KB Output is correct
16 Correct 320 ms 21108 KB Output is correct
17 Correct 330 ms 22048 KB Output is correct
18 Correct 389 ms 21836 KB Output is correct
19 Correct 485 ms 26348 KB Output is correct
20 Correct 424 ms 25020 KB Output is correct
21 Correct 231 ms 27968 KB Output is correct
22 Correct 241 ms 25956 KB Output is correct
23 Correct 274 ms 21928 KB Output is correct
24 Correct 280 ms 21820 KB Output is correct
25 Correct 411 ms 29072 KB Output is correct
26 Correct 391 ms 20376 KB Output is correct
27 Correct 371 ms 20664 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9676 KB Output is correct
2 Correct 53 ms 11240 KB Output is correct
3 Correct 46 ms 11208 KB Output is correct
4 Correct 60 ms 11460 KB Output is correct
5 Correct 54 ms 11672 KB Output is correct
6 Correct 48 ms 11364 KB Output is correct
7 Correct 38 ms 10564 KB Output is correct
8 Correct 240 ms 26880 KB Output is correct
9 Correct 258 ms 26964 KB Output is correct
10 Correct 35 ms 10512 KB Output is correct
11 Correct 373 ms 29796 KB Output is correct
12 Correct 404 ms 29988 KB Output is correct
13 Correct 324 ms 31104 KB Output is correct
14 Correct 34 ms 10440 KB Output is correct
15 Correct 299 ms 22372 KB Output is correct
16 Correct 320 ms 21108 KB Output is correct
17 Correct 330 ms 22048 KB Output is correct
18 Correct 389 ms 21836 KB Output is correct
19 Correct 485 ms 26348 KB Output is correct
20 Correct 424 ms 25020 KB Output is correct
21 Correct 231 ms 27968 KB Output is correct
22 Correct 241 ms 25956 KB Output is correct
23 Correct 274 ms 21928 KB Output is correct
24 Correct 280 ms 21820 KB Output is correct
25 Correct 411 ms 29072 KB Output is correct
26 Correct 391 ms 20376 KB Output is correct
27 Correct 371 ms 20664 KB Output is correct
28 Incorrect 35 ms 10204 KB Extra information in the output file
29 Halted 0 ms 0 KB -