oj.uz

Submission #441772

# Submission time Handle Problem Language Result Execution time Memory
441772 2021-07-06T04:26:12 Z 8e7 Inside information (BOI21_servers) C++17
50 / 100
 465 ms 28432 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <assert.h>
//#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, tc = 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;
			tc++;
			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);
	int act = 0;
	for (int i = 0;i < k;i++) {
		if (qtype[i]) cout << ans[i] << "\n", act++;
		else cout << (ans[i] ? "yes" : "no") << "\n";
	}
	assert(act == tc);
}
/*
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 34 ms 9596 KB Output is correct
2 Correct 47 ms 9888 KB Output is correct
3 Correct 44 ms 9732 KB Output is correct
4 Correct 48 ms 9984 KB Output is correct
5 Correct 47 ms 10224 KB Output is correct
6 Correct 46 ms 10040 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9596 KB Output is correct
2 Correct 47 ms 9888 KB Output is correct
3 Correct 44 ms 9732 KB Output is correct
4 Correct 48 ms 9984 KB Output is correct
5 Correct 47 ms 10224 KB Output is correct
6 Correct 46 ms 10040 KB Output is correct
7 Incorrect 35 ms 9340 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 9668 KB Output is correct
2 Correct 207 ms 24072 KB Output is correct
3 Correct 211 ms 24076 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9668 KB Output is correct
2 Correct 207 ms 24072 KB Output is correct
3 Correct 211 ms 24076 KB Output is correct
4 Incorrect 34 ms 9348 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 9584 KB Output is correct
2 Correct 397 ms 26972 KB Output is correct
3 Correct 420 ms 26976 KB Output is correct
4 Correct 315 ms 28432 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9584 KB Output is correct
2 Correct 397 ms 26972 KB Output is correct
3 Correct 420 ms 26976 KB Output is correct
4 Correct 315 ms 28432 KB Output is correct
5 Incorrect 33 ms 9332 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 33 ms 9596 KB Output is correct
2 Correct 308 ms 19604 KB Output is correct
3 Correct 323 ms 18440 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9596 KB Output is correct
2 Correct 308 ms 19604 KB Output is correct
3 Correct 323 ms 18440 KB Output is correct
4 Incorrect 35 ms 9360 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 9640 KB Output is correct
2 Correct 383 ms 26976 KB Output is correct
3 Correct 380 ms 27068 KB Output is correct
4 Correct 314 ms 28300 KB Output is correct
5 Correct 36 ms 9572 KB Output is correct
6 Correct 302 ms 19584 KB Output is correct
7 Correct 311 ms 18372 KB Output is correct
8 Correct 315 ms 19252 KB Output is correct
9 Correct 363 ms 19116 KB Output is correct
10 Correct 465 ms 23508 KB Output is correct
11 Correct 449 ms 22116 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9640 KB Output is correct
2 Correct 383 ms 26976 KB Output is correct
3 Correct 380 ms 27068 KB Output is correct
4 Correct 314 ms 28300 KB Output is correct
5 Correct 36 ms 9572 KB Output is correct
6 Correct 302 ms 19584 KB Output is correct
7 Correct 311 ms 18372 KB Output is correct
8 Correct 315 ms 19252 KB Output is correct
9 Correct 363 ms 19116 KB Output is correct
10 Correct 465 ms 23508 KB Output is correct
11 Correct 449 ms 22116 KB Output is correct
12 Incorrect 34 ms 9340 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 9708 KB Output is correct
2 Correct 47 ms 9908 KB Output is correct
3 Correct 45 ms 9800 KB Output is correct
4 Correct 50 ms 10008 KB Output is correct
5 Correct 48 ms 10308 KB Output is correct
6 Correct 46 ms 10024 KB Output is correct
7 Correct 34 ms 9652 KB Output is correct
8 Correct 200 ms 24120 KB Output is correct
9 Correct 220 ms 24072 KB Output is correct
10 Correct 34 ms 9540 KB Output is correct
11 Correct 368 ms 27020 KB Output is correct
12 Correct 394 ms 27060 KB Output is correct
13 Correct 317 ms 28240 KB Output is correct
14 Correct 34 ms 9636 KB Output is correct
15 Correct 312 ms 19612 KB Output is correct
16 Correct 317 ms 18380 KB Output is correct
17 Correct 317 ms 19180 KB Output is correct
18 Correct 393 ms 19004 KB Output is correct
19 Correct 452 ms 23548 KB Output is correct
20 Correct 417 ms 22216 KB Output is correct
21 Correct 249 ms 25112 KB Output is correct
22 Correct 261 ms 23144 KB Output is correct
23 Correct 286 ms 19252 KB Output is correct
24 Correct 267 ms 19004 KB Output is correct
25 Correct 385 ms 26172 KB Output is correct
26 Correct 346 ms 17560 KB Output is correct
27 Correct 330 ms 17712 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9708 KB Output is correct
2 Correct 47 ms 9908 KB Output is correct
3 Correct 45 ms 9800 KB Output is correct
4 Correct 50 ms 10008 KB Output is correct
5 Correct 48 ms 10308 KB Output is correct
6 Correct 46 ms 10024 KB Output is correct
7 Correct 34 ms 9652 KB Output is correct
8 Correct 200 ms 24120 KB Output is correct
9 Correct 220 ms 24072 KB Output is correct
10 Correct 34 ms 9540 KB Output is correct
11 Correct 368 ms 27020 KB Output is correct
12 Correct 394 ms 27060 KB Output is correct
13 Correct 317 ms 28240 KB Output is correct
14 Correct 34 ms 9636 KB Output is correct
15 Correct 312 ms 19612 KB Output is correct
16 Correct 317 ms 18380 KB Output is correct
17 Correct 317 ms 19180 KB Output is correct
18 Correct 393 ms 19004 KB Output is correct
19 Correct 452 ms 23548 KB Output is correct
20 Correct 417 ms 22216 KB Output is correct
21 Correct 249 ms 25112 KB Output is correct
22 Correct 261 ms 23144 KB Output is correct
23 Correct 286 ms 19252 KB Output is correct
24 Correct 267 ms 19004 KB Output is correct
25 Correct 385 ms 26172 KB Output is correct
26 Correct 346 ms 17560 KB Output is correct
27 Correct 330 ms 17712 KB Output is correct
28 Incorrect 35 ms 9428 KB Extra information in the output file
29 Halted 0 ms 0 KB -